题目链接：http://codeforces.com/contest/711/problem/C
题意：n个点染色，一共有m种颜色，要求原本有颜色不染色；染色结束后颜色相同算一段，要求一共有k段。每个点染每个颜色的花费是pij，问最小花费。
dp(i,j,k)表示i点涂第j个颜色的时候，并且有k段时的最小化费。
初始化，如果1是０的话，dp(1,1,i)=p(1,i)，否则dp(1,1,c(i))=0。
转移中要向后更新，加入更新到i点有颜色，则更新为dp[i][j][c[i]] = inf，先考虑同色，如果dp[i-1][j][c[i]]不为初始值，则更新dp[i][j][c[i]]，否则更新为dp[i][j][k] = inf。再枚举m个颜色，从与当前颜色不同并且是j-1个颜色的转移过来，dp[i][j][c[i]] = min(dp[i][j][c[i]], dp[i-1][j-1][k])。
如果i点是有颜色的，则要考虑两种不同颜色的转移。
1 #include <algorithm> 2 #include <iostream> 3 #include <iomanip> 4 #include <cstring> 5 #include <climits> 6 #include <complex> 7 #include <fstream> 8 #include <cassert> 9 #include <cstdio> 10 #include <bitset> 11 #include <vector> 12 #include <deque> 13 #include <queue> 14 #include <stack> 15 #include <ctime> 16 #include <set> 17 #include <map> 18 #include <cmath> 19 using namespace std; 20 #define fr first 21 #define sc second 22 #define cl clear 23 #define BUG puts("here!!!") 24 #define W(a) while(a--) 25 #define pb(a) push_back(a) 26 #define Rint(a) scanf("%d", &a) 27 #define Rll(a) scanf("%I64d", &a) 28 #define Rs(a) scanf("%s", a) 29 #define Cin(a) cin >> a 30 #define FRead() freopen("in", "r", stdin) 31 #define FWrite() freopen("out", "w", stdout) 32 #define Rep(i, len) for(int i = 0; i < (len); i++) 33 #define For(i, a, len) for(int i = (a); i < (len); i++) 34 #define Cls(a) memset((a), 0, sizeof(a)) 35 #define Clr(a, x) memset((a), (x), sizeof(a)) 36 #define Full(a) memset((a), 0x7f7f7f, sizeof(a)) 37 #define lrt rt << 1 38 #define rrt rt << 1 | 1 39 #define pi 3.14159265359 40 #define RT return 41 #define lowbit(x) x & (-x) 42 #define onecnt(x) __builtin_popcount(x) 43 typedef long long LL; 44 typedef long double LD; 45 typedef unsigned long long ULL; 46 typedef pair<int, int> pii; 47 typedef pair<string, int> psi; 48 typedef pair<LL, LL> pll; 49 typedef map<string, int> msi; 50 typedef vector<int> vi; 51 typedef vector<LL> vl; 52 typedef vector<vl> vvl; 53 typedef vector<bool> vb; 54 55 const int maxn = 110; 56 const LL inf = 1e16; 57 int n, m, K; 58 int c[maxn]; 59 int p[maxn][maxn]; 60 LL ret; 61 LL dp[maxn][maxn][maxn]; 62 63 int main() { 64 // FRead(); 65 while(~Rint(n)&&~Rint(m)&&~Rint(K)) { 66 Clr(dp, -1); ret = inf; 67 For(i, 1, n+1) Rint(c[i]); 68 For(i, 1, n+1) { 69 For(j, 1, m+1) { 70 Rint(p[i][j]); 71 } 72 } 73 if(c[1]) dp[1][1][c[1]] = 0; 74 else For(i, 1, m+1) dp[1][1][i] = p[1][i]; 75 For(i, 2, n+1) { 76 For(j, 1, K+1) { 77 if(c[i]) { 78 dp[i][j][c[i]] = inf; 79 if(dp[i-1][j][c[i]]!=-1) { 80 dp[i][j][c[i]] = dp[i-1][j][c[i]]; 81 } 82 For(k, 1, m+1) { 83 if(k != c[i] && dp[i-1][j-1][k] != -1) { 84 dp[i][j][c[i]] = min(dp[i][j][c[i]], dp[i-1][j-1][k]); 85 } 86 } 87 } 88 else { 89 For(k, 1, m+1) { 90 dp[i][j][k] = inf; 91 For(h, 1, m+1) { 92 if(h != k) { 93 if(dp[i-1][j-1][h] != -1) { 94 dp[i][j][k] = min(dp[i][j][k], dp[i-1][j-1][h]+p[i][k]); 95 } 96 } 97 else { 98 if(dp[i-1][j][h] != -1) { 99 dp[i][j][k] = min(dp[i][j][k], dp[i-1][j][h]+p[i][k]); 100 } 101 } 102 } 103 } 104 } 105 } 106 } 107 For(i, 1, m+1) { 108 if(dp[n][K][i] != -1) ret = min(ret, dp[n][K][i]); 109 } 110 if(ret >= inf) puts("-1"); 111 else cout << ret << endl; 112 } 113 RT 0; 114 }