/*
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-18;
// 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()){
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);
}
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
*/
static ll idx = 0;
idx = min(idx,(ll) lines.size() - 1);
while (idx + 1 < lines.size() && x <= lines[idx + 1].p + EPS){
// Đi dần về phía bên trái trục số
idx++;
}
return mp(lines[idx].a * x + lines[idx].b,lines[idx].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++){
lines.clear(); // Reset Convex Hull
// reset lai hang dp dang tinh
for (int i = 1 ; i < n ; i++){
dp[1][i] = 0;
}
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 = 0;
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:153:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
153 | while (idx + 1 < lines.size() && x <= lines[idx + 1].p + EPS){
| ~~~~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
contestant found the optimal answer: 108 == 108 |
| 2 |
Correct |
1 ms |
4444 KB |
contestant found the optimal answer: 999 == 999 |
| 3 |
Correct |
0 ms |
348 KB |
contestant found the optimal answer: 0 == 0 |
| 4 |
Correct |
1 ms |
4444 KB |
contestant found the optimal answer: 1542524 == 1542524 |
| 5 |
Correct |
1 ms |
6492 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 |
4444 KB |
contestant found the optimal answer: 100400096 == 100400096 |
| 10 |
Correct |
1 ms |
4444 KB |
contestant found the optimal answer: 900320000 == 900320000 |
| 11 |
Correct |
0 ms |
4444 KB |
contestant found the optimal answer: 3698080248 == 3698080248 |
| 12 |
Correct |
1 ms |
4444 KB |
contestant found the optimal answer: 3200320000 == 3200320000 |
| 13 |
Incorrect |
0 ms |
4444 KB |
contestant didn't find the optimal answer: 140067 < 140072 |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
contestant didn't find the optimal answer: 1092256 < 1093956 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
contestant didn't find the optimal answer: 407161746 < 610590000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
contestant didn't find the optimal answer: 20166072 < 21503404 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
5716 KB |
contestant didn't find the optimal answer: 1197227828 < 1818678304 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
13260 KB |
contestant didn't find the optimal answer: 13199711736 < 19795776960 |
| 2 |
Halted |
0 ms |
0 KB |
- |
