Submission #998527

#	Time	Username	Problem	Language	Result	Execution time	Memory
998527		ommivorous	Split the sequence (APIO14_sequence)	C++17	100 / 100	597 ms	86296 KiB

sequence

/*
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 (stderr)

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){
      |         ~~~~~~~~^~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 29 / 29