백준10067 수열 나누기

작성일 | In

문제 링크

  • http://icpc.me/10067

문제 출처

  • 2014 APIO 2번

사용 알고리즘

  • DP
  • Convex Hull Trick

시간복잡도

  • O(KN)

풀이

dp[k][n] = n번째 원소까지 k번 잘랐을 때 최대 점수
라고 정의를 하면
dp[k][n] = max( dp[k-1][i] + sum[i] * (sum[n] - sum[i]) )입니다.

dp[k][n] = max( sum[i] * sum[n] + dp[k-1][i] - sum[i] * sum[i] )로 보면, max 함수 내부의 식을 기울기가 sum[i]이고 y절편이 dp[k-1][i] - sum[i] * sum[i]인 일차함수꼴로 나타낼 수 있습니다.
Convex Hull Trick을 써줄 수 있습니다.

기울기가 같은 직선이 연속으로 들어오는 경우에는 y절편이 더 큰 직선만 남겨주면 됩니다.
MLE가 발행할 수 있는데, dp[k][]를 구할 때 dp[k-1][]만 사용한다는 점을 이용해 토글링을 해줄 수 있습니다.

정답을 역추적하는 것은, track[k][n] = dp[k][n]을 만족하는 i 처럼 정의해서 잘 따라가주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

struct CHT{
	ll a[101010], b[101010], c[101010];
	int pv, top;

	void init(){
		pv = top = 0;
	}

	ll f(ll idx, ll x){
		return a[idx]*x + b[idx];
	}

	void insert(ll aa, ll bb, ll cc){
		if(top >= 1 && aa == a[top-1]){
			c[top-1] = cc; return;
		}
		while(top >= 2 && (b[top-1] - b[top-2]) * (a[top-2] - aa) >= (bb - b[top-2]) * (a[top-2] - a[top-1])) top--;
		a[top] = aa;
		b[top] = bb;
		c[top] = cc;
		top++;
		if(pv >= top) pv = top - 1;
	}

	p get(ll x){
		while(pv+1 < top && a[pv+1]*x + b[pv+1] > a[pv]*x + b[pv]) pv++;
		return {f(pv, x), c[pv]};
	}
} cht;

ll arr[101010];
ll sum[101010];
ll dp[2][101010];
int track[222][101010];
vector<int> ans;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, k; cin >> n >> k;
	for(int i=1; i<=n; i++) cin >> arr[i], sum[i] = sum[i-1] + arr[i];

	for(int i=1; i<=k; i++){
		cht.init();
		cht.insert(0, 0, 0);
		for(int j=1; j<=n; j++){
			auto now = cht.get(sum[j]);
			dp[i&1][j] = now.x;
			track[i][j] = now.y;
			cht.insert(sum[j], dp[i-1&1][j] - sum[j] * sum[j], j);
		}
	}
	cout << dp[k&1][n] << "\n";

	int now = n;
	ans.push_back(-1);
	for(int i=k; i>=1; i--){
		ans.push_back(track[i][now]);
		now = track[i][now];
	}
	sort(all(ans));
	for(int i=1; i<=k; i++){
		if(!ans[i]) ans[i] = 1;
		if(ans[i] <= ans[i-1]) ans[i] = ans[i-1] + 1;
	}
	for(int i=1; i<=k; i++) cout << ans[i] << " ";
}