oj.uz

답안 #998527

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
998527 2024-06-14T07:31:17 Z ommivorous 수열 (APIO14_sequence) C++17
100 / 100
 597 ms 86296 KB 
/*
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){
      |         ~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 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

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 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

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 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

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 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

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 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

Subtask #6
29.0 / 29.0

# 결과 실행 시간 메모리 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