/*
APIO 2014 - Split the Sequence
https://oj.uz/problem/view/APIO14_sequence
Cho một mảng gồm N số và số K. Chúng ta phải chia mảng thành K + 1 đoạn không rỗng.
Hay nói cách khác, chúng ta phải làm 2 thao tác này K lần:
- Chọn một đoạn có >= 2 phần tử
- Chia nó thành hai đoạn không rỗng.
Ví dụ có đoạn [L..P P + 1 ..R] thì ta có thể chia nó thành hai đoạn: [L...P] và [P + 1 ...R]
Số điểm chúng ta nhận được đó khi làm thao tác này là (A[L] + A[L + 1] + ... + A[P]) * (A[P + 1] + ... + A[R])
Tìm tổng số điểm lớn nhất có thể đạt được sau khi thực hiện các thao tác cắt K lần.
Subtask 1: 1 < k < n <= 10. => Xét mọi trường hợp.
Chúng ta có thể làm điều này bằng cách xét mọi permutation của N, với mỗi permutation lấy K số đầu tiên
=> Lần lượt thực hiện các thao tác cắt này
=> Độ phức tạp ~ O(N!) => Chỉ cần cài backtrack cẩn thận là ok
Subtask 2: 1 < k < n <= 50
Để ý rằng sau mỗi thao tác cắt thì chúng ta lại có được các đoạn riêng biệt => Có thể xem đây giống như những bài toán con
=> DP theo kiểu đoạn [L.R]
=> dp[l][r][k] là số điểm lớn nhất có thể đạt được khi thực hiện K thao tác lên đoạn [L,R]
dp[l][r][k] = dp[l][p][k'] + dp[p + 1][r][k - 1 - k'] + (pre[p] - pre[l - 1]) * (pre[r] - pre[p])
với l <= p <= r và 0 <= k' <= k-1
Có tổng cộng O(N^2 * K) trạng thái
Với mỗi trạng thái dp[l][r][k] chúng ta cần O(N * K) để tính
=> Độ phức tạp tổng cộng là O(N^3 * K^2)
Subtask 3: 1 <= k < n <= 200
Có một quan sát rất quan trọng ở bài này chính là thứ tự cắt KHÔNG ẢNH HƯỞNG đến số điểm nhận được
Ví dụ:
[1,3,4,5,2,1] Giả sử cắt ở những vị trí sau [1,3|4|5|2,1]
[1,3,4,5,2,1] => [1,3] [4,5,2,1] => [1,3] [4] [5,2,1] => [1,3] [4] [5] [2,1]
[1,3,4,5,2,1] => [1,3,4,5] [2,1] => [1,3] [4,5] [2,1] => [1,3] [4] [5] [2,1]
Hai cách trên đều có số điểm như nhau => Chỉ cần quan tâm những vị trí cắt ở đâu.
Chứng minh:
Giả sử chúng ta có 3 đoạn A,B,C liền kề nhau như sau:
[A | B | C]
Ở đây chúng ta có hai cách cắt:
- Cách 1: [A B C] => [A B] [C] => [A] [B] [C] số điểm nhận được là C * (A + B) + A * B = AB + AC + BC
- Cách 2: [A B C] => [A] [B C] => [A] [B] [C] số điểm nhận được là A * (B + C) + B * C = AB + Ac + BC
=> Thứ tự không quan trọng => Cứ cắt theo thứ tự từ trái sang phải với các vị trí cho trước cũng chẳng sao
Khi đó chúng ta có thể có công thức DP như sau:
dp[k][i] là số điểm lớn nhất có thể đạt được sau K lát cắt, lát cắt cuối cùng là lát cắt giữa hai phần tử A[i] và A[i + 1]
dp[k][i] = dp[k - 1][j] + (pre[i] - pre[j]) * (pre[n] - pre[i]) với j < i
Lát cắt thứ K - 1 nằm ở vị trí j => Đoạn cuối cùng hiện tại là [A[j + 1] ... A[i] A[i + 1] ... A[N]]
Cắt ở giữa A[i] và A[i + 1] => [A[j + 1] ... A[i]] và [A[i + 1] .. A[N]]
=> Số điểm nhận được sau bước này là (pre[i] - pre[j]) * (pre[n] - pre[i])
=> Độ phức tạp là O(N^2 * K)
Thực ra với độ phức tạp này thì có thể giải được luôn cả Subtask 4
Sol full:
dp[k][i] = dp[k - 1][j] + (pre[i] - pre[j]) * (pre[n] - pre[i]) = -pre[j] * (pre[n] - pre[i]) + dp[k - 1][j] + pre[i] * (pre[n] - pre[i])
Thấy rằng -pre[j] * (pre[n] - pre[i]) + dp[k - 1][j] có thể dùng kỹ thuật Convex Hull để tính nhanh được
Để ý rằng mảng chỉ gồm các phần tử không âm => pre[j] tăng dần khi j tăng => -pre[j] giảm dần khi j tăng
=> Slope các đường được thêm vào giảm dần
Mặt khác pre[n] - pre[i] giảm dần khi i tăng => vị trí query giảm dần
=> Để tính được hàng thứ K thì ta chỉ mất O(N) => Độ phức tạp thời gian là O(K * N)
Tuy nhiên với N <= 10^5 và K <= min(N - 1,200) thì trong t/h xấu nhất cần đến mảng 10^7 => Không đủ bộ nhớ
=> Cần cải tiến thêm => Dùng trick tối ưu bộ nhớ
Để ý rằng khi tính hàng thứ K của mảng DP chúng ta chỉ cần sử dụng đến các giá trị DP ở hàng thứ K - 1
=> Chỉ cần lưu 2 hàng luôn phiên nhau (Hàng hiện tại đang tính và hàng gần nhất đã tính xong)
=> Chỉ cần mảng có kích thước 2 * 10^5 trong trường hợp xấu nhất
*/
#include <bits/stdc++.h>
#define fileopen(a, b) freopen(((std::string)a + ".inp").c_str(), "r", stdin); freopen(((std::string)b + ".out").c_str(), "w", stdout);
#define fileopen1(a) freopen(((std::string)a + ".inp").c_str(), "r", stdin); freopen(((std::string)a + ".out").c_str(), "w", stdout);
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<ll,ll> ii;
ll const mod = 1e9 + 7, MAXN = 1e5 + 1,oo = 3e18;
long double const EPS = 1e-9;
// Convex Hull
struct Line {
ll a,b,pos;
long double p; // Đường thẳng hiện tại sẽ có tác dụng trên đoạn (-oo,p]
};
vector<Line> lines;
long double getX (ll a1, ll b1, ll a2, ll b2){
// Lấy hoành độ giao điểm của y = a1 * x + b1, y = a2 * x + b2
return (long double) (b2 - b1) / (a1 - a2);
}
void add (ll a, ll b, ll pos){
// Các đường thẳng có slope giảm dần + đang muốn tìm Convex Hull Max => khi thêm đường này vào
// Nó sẽ có tác dụng trên đoạn (-oo,p]
long double p = oo;
while (!lines.empty()){
if (lines.back().a == a){
// Xét trường hợp hai đường thẳng có cùng Slope
if (lines.back().b >= b){
// Đường thẳng đang muốn thêm vào không bao giờ vượt trội hơn => Bỏ qua
return;
}
// Đường thẳng mới luôn vượt trội hơn lines.back() => Loại bỏ
lines.pop_back();
continue;
}
p = getX(lines.back().a,lines.back().b,a,b);
if (p > lines.back().p + EPS){
// EPS được dùng để tránh sai số, các số [a - EPS,a + EPS] đều được coi là bằng a
// Đoạn ở phía bên trái cùng hiện tại đang có tác dụng trên đoạn (-oo,lines.back().p]
// Nếu đoạn thẳng mới tốt hơn đoạn phía ngoài cùng trên đoạn (-oo,p] và p > lines.back().p => đoạn ngoài cùng vô dụng
lines.pop_back();
}
else {
// Đoạn ngoài cùng vẫn có ích
break;
}
}
Line cur; cur.a = a; cur.b = b; cur.p = p; cur.pos = pos;
lines.pb(cur);
}
ll pos = 0;
ii query (int x){
// Giả sử bây giờ vector lines có K đường thẳng
// Khoảng có tác dụng của các đường thẳng thứ K - 1, K - 2,..., 0 là
// (-oo,lines[k - 1].p] (lines[k - 1].p,lines[k - 2].p] ... (lines[0].p,oo]
/* Để ý rằng do slope giảm dần (có thể vẽ ra để dễ quan sát)
=> Đoạn có tác dụng của các đường được thêm vào sau càng ngày càng tiến về hướng -oo
Ví dụ vector trên nếu thêm một đường thứ K + 1 (giả sử đường thứ K vẫn được sử dụng) thì đoạn có tác dụng của các đường là
(-oo,lines[k].p] (lines[k].p,lines[k - 1].p] (lines[k - 1].p,lines[k - 2].p] ... (lines[0].p,oo]
Mặt khác, như đã giải thích ở đầu file, các vị trí chúng ta query giảm dần
=> Nếu query trước có đáp án dùng đường thẳng thứ i thì chúng ta không cần quan tâm i - 1 đường thẳng đầu tiên nữa
*/
pos = min(pos,(ll) lines.size() - 1);
while (pos + 1 < lines.size() && x <= lines[pos + 1].p + EPS){
// Đi dần về phía bên trái trục số
pos++;
}
return mp(lines[pos].a * x + lines[pos].b,lines[pos].pos);
}
// Solving
ll tc,n,m;
ll a[MAXN],pre[MAXN];
int trace[201][MAXN];
ll dp[2][MAXN]; // dp[0][.] là hàng dp trước, dp[1][.] là hàng dp đang tính hiện tại
void caau(){
// calm
cin >> n >> m;
for (int i = 1 ; i <= n ; i++){
cin >> a[i];
pre[i] = pre[i - 1] + a[i];
}
// Base case
// Calculate dp[1][.]
for (int i = 1 ; i < n ; i++){
dp[0][i] = (pre[n] - pre[i]) * pre[i];
}
for (int k = 2 ; k <= m ; k++){
// Reset Convex Hull
lines.clear(); pos = 0;
// reset lai hang dp dang tinh
for (int i = 1 ; i < n ; i++){
dp[1][i] = -oo;
}
for (int i = k ; i < n ; i++){
add(-pre[i - 1],dp[0][i - 1],i - 1);
ii que = query(pre[n] - pre[i]);
dp[1][i] = pre[i] * (pre[n] - pre[i]) + que.fi;
trace[k][i] = que.se;
}
// Sau khi tính xong hàng hiện tại thì lưu lại
for (int i = 1 ; i < n ; i++){
dp[0][i] = dp[1][i];
}
}
ll ans = -oo; ll trace_pos = -1;
for (int i = 1 ; i < n ; i++){
if (dp[0][i] > ans){
ans = dp[0][i];
trace_pos = i;
}
}
cout << ans << "\n";
for (int i = m ; i >= 1 ; i--){
cout << trace_pos << " ";
trace_pos = trace[i][trace_pos];
}
}
signed main() {
#ifdef thisiscaau
fileopen("input", "output");
#endif
#ifndef thisiscaau
// fileopen1("LAH");
#endif
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
tc = 1;
while (tc--) caau();
}
Compilation message
sequence.cpp: In function 'ii query(int)':
sequence.cpp:167:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
167 | while (pos + 1 < lines.size() && x <= lines[pos + 1].p + EPS){
| ~~~~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
contestant found the optimal answer: 108 == 108 |
| 2 |
Correct |
0 ms |
348 KB |
contestant found the optimal answer: 999 == 999 |
| 3 |
Correct |
0 ms |
348 KB |
contestant found the optimal answer: 0 == 0 |
| 4 |
Correct |
0 ms |
348 KB |
contestant found the optimal answer: 1542524 == 1542524 |
| 5 |
Correct |
0 ms |
348 KB |
contestant found the optimal answer: 4500000000 == 4500000000 |
| 6 |
Correct |
0 ms |
348 KB |
contestant found the optimal answer: 1 == 1 |
| 7 |
Correct |
0 ms |
348 KB |
contestant found the optimal answer: 1 == 1 |
| 8 |
Correct |
0 ms |
348 KB |
contestant found the optimal answer: 1 == 1 |
| 9 |
Correct |
0 ms |
348 KB |
contestant found the optimal answer: 100400096 == 100400096 |
| 10 |
Correct |
0 ms |
348 KB |
contestant found the optimal answer: 900320000 == 900320000 |
| 11 |
Correct |
0 ms |
348 KB |
contestant found the optimal answer: 3698080248 == 3698080248 |
| 12 |
Correct |
0 ms |
348 KB |
contestant found the optimal answer: 3200320000 == 3200320000 |
| 13 |
Correct |
0 ms |
348 KB |
contestant found the optimal answer: 140072 == 140072 |
| 14 |
Correct |
0 ms |
348 KB |
contestant found the optimal answer: 376041456 == 376041456 |
| 15 |
Correct |
0 ms |
344 KB |
contestant found the optimal answer: 805 == 805 |
| 16 |
Correct |
0 ms |
348 KB |
contestant found the optimal answer: 900189994 == 900189994 |
| 17 |
Correct |
0 ms |
348 KB |
contestant found the optimal answer: 999919994 == 999919994 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
contestant found the optimal answer: 1093956 == 1093956 |
| 2 |
Correct |
0 ms |
348 KB |
contestant found the optimal answer: 302460000 == 302460000 |
| 3 |
Correct |
0 ms |
600 KB |
contestant found the optimal answer: 122453454361 == 122453454361 |
| 4 |
Correct |
0 ms |
348 KB |
contestant found the optimal answer: 93663683509 == 93663683509 |
| 5 |
Correct |
0 ms |
348 KB |
contestant found the optimal answer: 1005304678 == 1005304678 |
| 6 |
Correct |
0 ms |
348 KB |
contestant found the optimal answer: 933702 == 933702 |
| 7 |
Correct |
0 ms |
604 KB |
contestant found the optimal answer: 25082842857 == 25082842857 |
| 8 |
Correct |
0 ms |
348 KB |
contestant found the optimal answer: 687136 == 687136 |
| 9 |
Correct |
0 ms |
348 KB |
contestant found the optimal answer: 27295930079 == 27295930079 |
| 10 |
Correct |
0 ms |
348 KB |
contestant found the optimal answer: 29000419931 == 29000419931 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
contestant found the optimal answer: 610590000 == 610590000 |
| 2 |
Correct |
0 ms |
348 KB |
contestant found the optimal answer: 311760000 == 311760000 |
| 3 |
Correct |
1 ms |
1372 KB |
contestant found the optimal answer: 1989216017013 == 1989216017013 |
| 4 |
Correct |
0 ms |
348 KB |
contestant found the optimal answer: 1499437552673 == 1499437552673 |
| 5 |
Correct |
1 ms |
1116 KB |
contestant found the optimal answer: 1019625819 == 1019625819 |
| 6 |
Correct |
1 ms |
1372 KB |
contestant found the optimal answer: 107630884 == 107630884 |
| 7 |
Correct |
1 ms |
1372 KB |
contestant found the optimal answer: 475357671774 == 475357671774 |
| 8 |
Correct |
0 ms |
604 KB |
contestant found the optimal answer: 193556962 == 193556962 |
| 9 |
Correct |
1 ms |
600 KB |
contestant found the optimal answer: 482389919803 == 482389919803 |
| 10 |
Correct |
1 ms |
600 KB |
contestant found the optimal answer: 490686959791 == 490686959791 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
604 KB |
contestant found the optimal answer: 21503404 == 21503404 |
| 2 |
Correct |
0 ms |
604 KB |
contestant found the optimal answer: 140412195 == 140412195 |
| 3 |
Correct |
6 ms |
2140 KB |
contestant found the optimal answer: 49729674225461 == 49729674225461 |
| 4 |
Correct |
0 ms |
600 KB |
contestant found the optimal answer: 37485571387523 == 37485571387523 |
| 5 |
Correct |
5 ms |
2136 KB |
contestant found the optimal answer: 679388326 == 679388326 |
| 6 |
Correct |
5 ms |
1932 KB |
contestant found the optimal answer: 4699030287 == 4699030287 |
| 7 |
Correct |
6 ms |
2136 KB |
contestant found the optimal answer: 12418819758185 == 12418819758185 |
| 8 |
Correct |
6 ms |
2140 KB |
contestant found the optimal answer: 31093317350 == 31093317350 |
| 9 |
Correct |
2 ms |
860 KB |
contestant found the optimal answer: 12194625429236 == 12194625429236 |
| 10 |
Correct |
3 ms |
1116 KB |
contestant found the optimal answer: 12345131038664 == 12345131038664 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1368 KB |
contestant found the optimal answer: 1818678304 == 1818678304 |
| 2 |
Correct |
1 ms |
1368 KB |
contestant found the optimal answer: 1326260195 == 1326260195 |
| 3 |
Correct |
53 ms |
9904 KB |
contestant found the optimal answer: 4973126687469639 == 4973126687469639 |
| 4 |
Correct |
2 ms |
1624 KB |
contestant found the optimal answer: 3748491676694116 == 3748491676694116 |
| 5 |
Correct |
39 ms |
6456 KB |
contestant found the optimal answer: 1085432199 == 1085432199 |
| 6 |
Correct |
44 ms |
7248 KB |
contestant found the optimal answer: 514790755404 == 514790755404 |
| 7 |
Correct |
48 ms |
7644 KB |
contestant found the optimal answer: 1256105310476641 == 1256105310476641 |
| 8 |
Correct |
36 ms |
6608 KB |
contestant found the optimal answer: 3099592898816 == 3099592898816 |
| 9 |
Correct |
39 ms |
7328 KB |
contestant found the optimal answer: 1241131419367412 == 1241131419367412 |
| 10 |
Correct |
51 ms |
8912 KB |
contestant found the optimal answer: 1243084101967798 == 1243084101967798 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
10184 KB |
contestant found the optimal answer: 19795776960 == 19795776960 |
| 2 |
Correct |
15 ms |
10172 KB |
contestant found the optimal answer: 19874432173 == 19874432173 |
| 3 |
Correct |
538 ms |
86296 KB |
contestant found the optimal answer: 497313449256899208 == 497313449256899208 |
| 4 |
Correct |
15 ms |
9932 KB |
contestant found the optimal answer: 374850090734572421 == 374850090734572421 |
| 5 |
Correct |
597 ms |
85300 KB |
contestant found the optimal answer: 36183271951 == 36183271951 |
| 6 |
Correct |
414 ms |
61820 KB |
contestant found the optimal answer: 51629847150471 == 51629847150471 |
| 7 |
Correct |
475 ms |
66664 KB |
contestant found the optimal answer: 124074747024496432 == 124074747024496432 |
| 8 |
Correct |
362 ms |
55728 KB |
contestant found the optimal answer: 309959349080800 == 309959349080800 |
| 9 |
Correct |
383 ms |
62128 KB |
contestant found the optimal answer: 124113525649823701 == 124113525649823701 |
| 10 |
Correct |
493 ms |
78000 KB |
contestant found the optimal answer: 124309619349406845 == 124309619349406845 |
