Codeforces 711 C. Coloring Trees (dp)

题目链接：http://codeforces.com/problemset/problem/711/C

给你n棵树，m种颜色，k是指定最后的完美值。接下来一行n个数表示1~n树原本的颜色，0的话就是没颜色(一定要上色)，非0就是有颜色（不能上色）。

接下来n行每行m个数，第i行第j个数表示编号为i的树上第j种颜色的代价为a[i][j]。

问你最后要使完美值为k的上色代价最小为多少，要是不可能的话就为-1。

我们来考虑dp，每个树和前一个树有联系。

dp[i][j][x] 表示第i棵树完美值为j 上第x种颜色的最小代价。

如果前一个树颜色和此树颜色相同，dp[i - 1][j][x] --> dp[i][j][x]

否则，dp[i - 1][j][y] --> dp[i][j + 1][x]

 1 //#pragma comment(linker, "/STACK:102400000, 102400000")
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <cstdlib>
 5 #include <cstring>
 6 #include <cstdio>
 7 #include <vector>
 8 #include <cmath>
 9 #include <ctime>
10 #include <list>
11 #include <set>
12 #include <map>
13 using namespace std;
14 typedef __int64 LL;
15 typedef pair <int, int> P;
16 const int N = 1e2 + 5;
17 LL dp[N][N][N], a[N][N], val[N], INF = 1e16;
18 //dp[i][k][j]  i棵树 k完美值 j颜色
19 
20 int main()
21 {
22     LL n, k, m;
23     scanf("%lld %lld %lld", &n, &m, &k);
24     for(LL i = 1; i <= n; ++i)
25         scanf("%lld", val + i);
26     for(LL i = 1; i <= n; ++i) {
27         for(LL j = 1; j <= m; ++j) {
28             scanf("%lld", &a[i][j]);
29         }
30     }
31     for(int i = 1; i <= n; ++i) {
32         for(int j = 1; j <= k; ++j) {
33             for(int x = 1; x <= m; ++x) {
34                 dp[i][j][x] = INF;
35             }
36         }
37     }
38     if(val[1]) { //已有颜色
39         dp[1][1][val[1]] = 0;
40     } else {
41         for(LL i = 1; i <= m; ++i) {
42             dp[1][1][i] = a[1][i];
43         }
44     }
45     for(LL i = 2; i <= n; ++i) {
46         for(LL j = 1; j <= k; ++j) {
47             for(LL x = 1; x <= m; ++x) {
48                 if(dp[i - 1][j][x] == INF)
49                     continue;
50                 if(val[i]) { 
51                     if(val[i] == x) { //与前一个颜色一致
52                         dp[i][j][val[i]] = min(dp[i - 1][j][x], dp[i][j][val[i]]);
53                     } else {
54                         dp[i][j + 1][val[i]] = min(dp[i - 1][j][x], dp[i][j + 1][val[i]]);
55                     }
56                 } else {
57                     for(LL y = 1; y <= m; ++y) {
58                         if(y == x) {
59                             dp[i][j][y] = min(dp[i][j][y], dp[i - 1][j][x] + a[i][y]);
60                         } else {
61                             dp[i][j + 1][y] = min(dp[i][j + 1][y], dp[i - 1][j][x] + a[i][y]);
62                         }
63                     }
64                 }
65             }
66         }
67     }
68     LL res = INF;
69     for(LL i = 1; i <= m; ++i) {
70         if(dp[n][k][i] == -1)
71             continue;
72         res = min(res, dp[n][k][i]);
73     }
74     printf("%lld
", res == (LL)INF ? -1: res);
75     return 0;
76 }