APIO

APIO 2010 特别行动队 (commando)

Posted in APIO on 五月 19th, 2010 by 纳米 – 1 Comment

解题报告：
解法一：
设f(x)为1 – x所得最大分数，c[x]为第x人分数，sum[x]为1-x总分。
有方程：f(x) = max{f(i) + w[i+1, x] | 0 <= i < x}，其中w[i, j] = a*(sum[j] – sum[i-1])^2 + b*(sum[j] – sum[i-1]) + c。

首先证明w[i, j] + w[i+1, j+1] >= w[i+1, j] + w[i, j+1]：
(1) w[i, j+1] – w[i, j]
=a*(sum[j] – sum[i-1] + c[j+1])^2 + b*(sum[j] – sum[i-1] + c[j+1]) + c – a*(sum[j] – sum[i-1])^2 – b*(sum[j] – sum[i-1]) – c
=a*(sum[j] – sum[i-1])^2 + a*c[j+1]^2 + 2*a*(sum[j] – sum[i-1])*c[j+1] + b*(sum[j] – sum[i-1]) + b*c[j+1] + c – a*(sum[j] – sum[i-1])^2 – b*(sum[j] – sum[i-1]) – c
=a*c[j+1]^2 + b*c[j+1] + 2*a*(sum[j] – sum[i-1])*c[j+1]
因为a*c[j+1]^2 + b*c[j+1]为常量，sum[j] – sum[i-1]关于i单调递减，a<0，c[j+1]>0，所以上述结果关于i单调递增。
(2) 同理，w[i, j] – w[i+1, j]关于j单调递减。
综上，w[i, j] + w[i+1, j+1] >= w[i+1, j] + w[i, j+1]。

时间复杂度O(n log2 n)，最后两个点本机（Intel Pentium E2140 1.6GHz）1.2s通过。

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
76
77
78
79
80
81
82
83
84
85

#include <stdio.h>
 
const char IN_FILE_NAME[] = "commando.in";
const char OUT_FILE_NAME[] = "commando.out";
 
const int maxn = 1000005;
int n, _a, _b, _c, data[maxn], stack[maxn][3], last;
long long a, b, c, sum[maxn], dp[maxn], answer;
 
int input() {
	FILE *fin = fopen(IN_FILE_NAME, "r");
	fscanf(fin, "%d%d%d%d", &n, &_a, &_b, &_c);
	for (int i = 1; i <= n; ++i)
		fscanf(fin, "%d", &data[i]);
	fclose(fin);
	return 0;
}
 
int work_init() {
	sum[0] = 0;
	for (int i = 1; i <= n; ++i)
		sum[i] = sum[i-1] + data[i];
	a = _a, b = _b, c = _c;
	return 0;
}
 
long long calc_dp(int i, int j) {
	return dp[j] + a * (sum[i] - sum[j]) * (sum[i] - sum[j]) + b * (sum[i] - sum[j]) + c;
}
 
int work_find(int t0, int t1, int w0, int w1) {
	int left = w0, right = w1, res = w1 + 1;
	while (left <= right) {
		int mid = (left + right) >> 1;
		if (mid > t0 && calc_dp(mid, t0) >= calc_dp(mid, t1)) {
			res = mid;
			right = mid - 1;
		} else {
			left = mid + 1;
		}
	}
	return res;
}
 
int work_dp() {
	dp[0] = last = 0;
	stack[0][0] = 0;
	stack[0][1] = 1;
	stack[0][2] = n;
	int pw = 0;
	for (int i = 1; i <= n; ++i) {
		if (pw > last)
			pw = last;
		while (i > stack[pw][2])
			++pw;
		dp[i] = calc_dp(i, stack[pw][0]);
		while (stack[last][2] > i && calc_dp(stack[last][1], i) >= calc_dp(stack[last][1], stack[last][0]))
			--last;
		int w = work_find(i, stack[last][0], stack[last][1], stack[last][2]);
		if (w <= n) {
			stack[last][2] = w - 1;
			++last;
			stack[last][0] = i;
			stack[last][1] = w;
			stack[last][2] = n;
		}
	}
	answer = dp[n];
	return 0;
}
 
int output() {
	FILE *fout = fopen(OUT_FILE_NAME, "w");
	fprintf(fout, "%lld\n", answer);
	fclose(fout);
	return 0;
}
 
int main() {
	input();
	work_init();
	work_dp();
	output();
	return 0;
}

解法二：
f(n) = max{f(i) + a*(sum[n] – sum[i])^2 + b*(sum[n] – sum[i]) + c | 0 <= i < x}
= max{f(i) + a*sum[n]^2 + b*sum[i]^2 – 2*a*sum[n]*sum[i] + b*sum[n] – b*sum[i] + c | 0 <= i < x}
= max{f(i) + b*sum[i]^2 – 2*a*sum[n]*sum[i] – b*sum[i] | 0 <= i < x} + a*sum[n]^2 + b*sum[n] + c
不妨设a(i) = -2*a*sum[n], x(i) = sum[i], y(i) = f(i) + b*sum[i]^2 – b*sum[i]
原式 = max{a(i)*x(i) + y(i) | 0 <= i < x} + a*sum[n]^2 + b*sum[n] + c x(i)是单调递减的，-a(i)也是单调递减的（考虑P = ax + y => y = -ax + P，最大化截距P）。显然，所有决策点都在凸包上。所以，维护一个栈，进行决策点储存。具体见论文《1D/1D动态规划优化初步》。
时间复杂度为O(n)。最后两个数据点本机500ms通过。

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
76
77
78

#include <stdio.h>
 
const char IN_FILE_NAME[] = "commando.in";
const char OUT_FILE_NAME[] = "commando.out";
 
const int maxn = 1000005;
int n, _a, _b, _c, data[maxn], stack[maxn], last;
long long a, b, c, sum[maxn], stackp[maxn][2], dp[maxn], answer;
 
int input() {
	FILE *fin = fopen(IN_FILE_NAME, "r");
	fscanf(fin, "%d%d%d%d", &n, &_a, &_b, &_c);
	for (int i = 1; i <= n; ++i)
		fscanf(fin, "%d", &data[i]);
	fclose(fin);
	return 0;
}
 
int work_init() {
	sum[0] = 0;
	for (int i = 1; i <= n; ++i)
		sum[i] = sum[i-1] + data[i];
	a = _a, b = _b, c = _c;
	return 0;
}
 
long long calc(int i, int j) {
	return dp[j] + a * (sum[i] - sum[j]) * (sum[i] - sum[j]) + b * (sum[i] - sum[j]) + c;
}
 
void stack_insert(int t, long long x, long long y) {
	stack[++last] = t;
	stackp[last][0] = x;
	stackp[last][1] = y;
}
 
bool insert_ok(long long x2, long long y2) {
	long long x0 = stackp[last-1][0], y0 = stackp[last-1][1];
	long long x1 = stackp[last][0], y1 = stackp[last][1];
	return (x1-x0)*(y2-y0)-(x2-x0)*(y1-y0) < 0;
}
 
int work_dp() {
	dp[0] = 0;
	dp[1] = calc(1, 0);
	last = -1;
	stack_insert(0, sum[0], dp[0]+a*sum[0]*sum[0]-b*sum[0]);
	stack_insert(1, sum[1], dp[1]+a*sum[1]*sum[1]-b*sum[1]);
	int pw = 0;
	for (int i = 2; i <= n; ++i) {
		pw = pw < last ? pw : last;
		while (pw < last && calc(i, stack[pw+1]) >= calc(i, stack[pw]))
			++pw;
		dp[i] = calc(i, stack[pw]);
		if (i < n) {
			while (last > 0 && !insert_ok(sum[i], dp[i]+a*sum[i]*sum[i]-b*sum[i]))
				--last;
			stack_insert(i, sum[i], dp[i]+a*sum[i]*sum[i]-b*sum[i]);
		}
	}
	answer = dp[n];
	return 0;
}
 
int output() {
	FILE *fout = fopen(OUT_FILE_NAME, "w");
	fprintf(fout, "%lld\r\n", answer);
	fclose(fout);
	return 0;
}
 
int main() {
	input();
	work_init();
	work_dp();
	output();
	return 0;
}