首页 > 代码库 > Codeforces Round #369 (Div. 2) C. Coloring Trees DP
Codeforces Round #369 (Div. 2) C. Coloring Trees DP
C. Coloring Trees
链接：
http://codeforces.com/problemset/problem/711/C
题意：
给你nn棵树，如果cici为0的话，那么这棵树就没有上色，否则这棵树就是cici颜色的。
相同颜色的树会被当成一段，现在你要恰好刷漆刷成k段，问你最小花费是多少。
把第i棵树刷漆刷成j颜色的花费为p[i][j]
题解：
dp[i][j][k]表示第i棵树，刷成了j颜色，当前有k段的最小花费是多少。
然后好礼n^4转移就好了，很容易就能够优化成空间n^2,时间n^3的。
不优化也能过。
代码：
1 #include<iostream> 2 #include<algorithm> 3 #define LL long long 4 #define inf 1e17+1 5 using namespace std; 6 7 const int maxn = 100 + 10; 8 LL p[maxn][maxn]; 9 LL dp[maxn][maxn][maxn];10 int c[maxn];11 12 int main()13 {14 int n, m, kk;15 cin >> n >> m >> kk;16 for (int i = 1; i <= n; i++)17 cin >> c[i];18 for (int i = 1; i <= n; i++)19 for (int j = 1; j <= m; j++)20 cin >> p[i][j];21 for (int i = 0; i <= 100; i++)22 for (int j = 0; j <= 100; j++)23 for (int k = 0; k <= 100; k++)24 dp[i][j][k] = inf;25 dp[0][0][0] = 0;26 for (int i = 1; i <= n; i++)27 if (c[i] != 0)28 for (int j = 0; j <= m; j++)29 for (int k = 0; k <= i; k++)30 if (c[i] == j)31 dp[i][c[i]][k] = min(dp[i - 1][j][k], dp[i][c[i]][k]);32 else33 dp[i][c[i]][k + 1] = min(dp[i - 1][j][k], dp[i][c[i]][k + 1]);34 else35 for (int t = 1; t <= m; t++)36 for (int j = 0; j <= m; j++)37 for (int k = 0; k <= i; k++)38 if (t == j)39 dp[i][t][k] = min(dp[i - 1][j][k] + p[i][t], dp[i][t][k]);40 else41 dp[i][t][k + 1] = min(dp[i - 1][j][k] + p[i][t], dp[i][t][k + 1]);42 LL ans = inf;43 for (int i = 0; i <= m; i++)44 ans = min(dp[n][i][kk], ans);45 if (ans == inf)46 cout << "-1" << endl;47 else48 cout << ans << endl;49 return 0;50 }
Codeforces Round #369 (Div. 2) C. Coloring Trees DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。