| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
CTNCLN - Chia nhóm |
Cho N số nguyên dương A1,A2...An. Mỗi số có giá trị không vượt quá N .
Yêu cầu :
Hãy chia N số này thành một số nhóm sao cho:
-Mỗi nhóm là một dãy các số liên tiếp.
-Trọng số của mỗi nhóm được tính theo công thức : Bình phương của số giá trị khác nhau trong nhóm đó.
VD + 1 2 3 -> số giá trị khác nhau bằng 3 .
+ 1 2 1 -> số giá trị khác nhau bằng 2.
+ 1 1 1 -> số giá trị khác nhau bằng 1.
+Trọng số của dãy số bằng Tổng trọng số của tất cả các nhóm . Hãy tìm cách chia sao cho Tổng trọng số đạt giátrị nhỏ nhất.
Input
Dòng 1 : Gồm 2 số N và M - Số lượng số và số giá trị khác nhau trong dãy.
Dòng 2..N+1 : Mỗi dòng chứa một ố nguyên .
Output
Trọng số nhỏ nhất của dãy số.
Example
Input:13 4Output:
1
2
1
3
2
2
3
4
3
4
3
1
4
11
Giải thích : Chúng ta sẽ chia dãy ố thành 8 nhóm
+ 4 nhóm đầu tiên mỗi nhóm chứa một số duy nhất.
+ nhóm thứ 5 chứa hai số nguyên đều có giá trị là 2.
+ nhóm thứ 6 gồm các số từ 7->12 : (3, 4, 3, 4, 3)
+ 2 nhóm cuối cùng mỗi nhóm gồm 1 số duy nhất.
Kết quả là 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 2^2 + 1^2 + 1^2= 11.
Giới hạn: N<=40000.
| Được gửi lên bởi: | Phan Công Minh |
| Ngày: | 2009-09-17 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET |
| Nguồn bài: | Được add lên bởi canhteo |
hide comments
|
2017-09-27 09:46:36
Code tham khảo: http://123link.top/CTNCLN |
|
|
2017-09-13 07:38:30
Code AC: http://shink.in/PMchb |
|
|
2017-02-27 14:21:44
theo đề từ USACO thì giá trị lớn nhất của dãy ko vượt quá M @phanduy16 |
|
|
2014-07-23 14:33:53 Lollipop
cho M là gì vậy ?? |
|
|
2012-12-08 07:37:54 Shinken Yellow
M<= ? vậy |
|
|
2011-04-06 11:43:22 T-7
Hình như mỗi số có giá trị không quá M thì đúng hơn :D |
|
|
2011-03-19 06:48:30 Tran Dang Tuan Anh
Bài này nguồn từ USACO thì phải :d |
RSS