2010年02月13日星期六.sgu183
sgu183:根据单调性优化的dp
一开始想的挺好，二维状态，第一维是染第i个，第二维表示染了第i-j个。
题目要求要在任何的连续m个球中都有两个染色的，那么边界条件就是
染了第i个，i-m个，和他们中间的某个，这样就能抱枕任何的连续m个球都有两个。
然后写了个dp，华丽丽的tle@test 50 ...
1 const int N = 10010;
2 const int M = 101;
3 const int inf = 1 << 30;
4 int cost[N], n, m;
5 int dp[N][M];
6
7 int main()
8 {
9 int i, j, k;
10 scanf("%d%d", &n, &m);
11 for (i = 1; i <= n; i++) {
12 scanf("%d", cost + i);
13 }
14 for (i = 0; i < N; i++) {
15 for (j = 0; j < M; j++) {
16 dp[i][j] = inf;
17 }
18 }
19 dp[0][0] = 0;
20 for (i = 1; i <= n + 1; i++) {
21 for (j = 0; i - j >= 0 && j <= m; j++) {
22 for (k = 0; i - j - k >= 0 && j + k <= m; k++) {
23 if (dp[i - j][k] < inf) {
24 dp[i][j] = min(dp[i][j], dp[i - j][k] + cost[i]);
25 }
26 }
27 }
28 }
29 int res = inf;
30 for (j = 0; j <= m; j++) {
31 res = min(res, dp[n + 1][j]);
32 }
33 printf("%d\n", res);
34
35 }
这也难怪，复杂度是N * M * M = 10 ^ 9;
然后我就像，可怎么办。我就开始憋。
观察上面的dp可以看出 dp[i][j]是按照从j从小到达的顺序计算的，
而k也是按照从小到达转移的，也就是
dp[i][j] 来自dp[i-j][0],dp[i-j][1]...dp[i-j][i-m]
那么我们就可以让dp[i][j] 保存dp[i][0] ...dp[i][j]的最小值，那么
在后来的转移时用到dp[i][j]当做边界时只需要O(1) 的转移了。总的复杂度就变成了
N*M = 10 ^ 7 ，恩应该没问题了。
更形象话的解释
dp[i-j][0] dp[i-j][1] ... dp[i-j][i-m]
dp[i][j]逐一检查上述的值，选出最小的。
现在dp[i][j] 表示dp[i][0 ... j]中的最小值.
dp[i][j]只要检查检查dp[i-j][i-m] 和 dp[i][j-1]即可。
1
2 const int N = 10010;
3 const int M = 101;
4 const int inf = 1 << 30;
5 int cost[N], n, m;
6 int dp[N][M];
7
8 int main()
9 {
10 int i, j, k;
11 scanf("%d%d", &n, &m);
12 for (i = 1; i <= n; i++) { scanf("%d", cost + i); }
13 for (i = 1; i < N; i++) {
14 for (j = 0; j < M; j++) {
15 dp[i][j] = inf;
16 }
17 }
18 for (j = 0; j < M; j++) { dp[0][j] = 0; }
19 for (i = 1; i <= n + 1; i++) {
20 for (j = 1; i - j >= 0 && j <= m; j++) {
21 int k = (i > m) ? m-j : i-j;
22 if (dp[i-j][k] < inf) {
23 dp[i][j] = dp[i-j][k] + cost[i];
24 }
25 if (dp[i][j] > dp[i][j-1])
26 dp[i][j] = dp[i][j-1];
27 }
28 }
29 printf("%d\n", dp[n+1][m]);
30 }
31
32