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