题意:有n棵树,m种颜色,让你分成k段,数字0代表该树没没有进行染色,需要你从m种颜色中选择一个为其染色,染色的过程中需要消耗代价,求最小代价(已有颜色不必再染色)
dp[i][j][k] 表第i个位置颜色为j分为k分的最小代价
然后分类讨论:
情况1:col[i]和col[i - 1]都存在
情况2: col[i]存在,col[i - 1]不存在
情况3: col[i]不存在,col[i - 1]不存在
情况4:col[i]和col[i - 1]都不存在
#include <bits/stdc++.h> using namespace std; const int maxn = 105; typedef long long ll; const ll inf = 1e18; ll col[maxn]; ll dp[maxn][maxn][maxn], w[maxn][maxn]; int main() { int n, m, k; cin >> n >> m >> k; for (int i = 1; i <= n; i++) { cin >> col[i]; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> w[i][j]; } } for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) { for (int v = 0; v <= k; v++) { dp[i][j][v] = inf; } } } if (col[1]) { dp[1][col[1]][1] = 0; } else { for (int i = 1; i <= m; i++) dp[1][i][1] = w[1][i]; } for (int i = 2; i <= n; i++) { for (int j = 1; j <= m; j++) { // 当前位置 for (int v = 1; v <= m; v++) { //前一个位置 for (int u = 1; u <= k; u++) { //分为几块 if (col[i] && col[i - 1]) { //对应情况1 if (col[i] == col[i - 1]) { //如果当前颜色与前一个颜色相同 dp[i][col[i]][u] = min(dp[i][col[i]][u], dp[i - 1][col[i - 1]][u]); } else { //如果当前颜色与前一个颜色不相同 dp[i][col[i]][u + 1] = min(dp[i][col[i]][u + 1], dp[i - 1][col[i - 1]][u]); } } else if (col[i]) {//对于情况2 if (col[i] == v) { //如果当前颜色与前一个颜色相同 dp[i][col[i]][u] = min(dp[i][col[i]][u], dp[i - 1][v][u]); } else { //如果当前颜色与前一个颜色不相同 dp[i][col[i]][u + 1] = min(dp[i][col[i]][u + 1], dp[i - 1][v][u]); } } else if (col[i - 1]) { if (j == col[i - 1]) { dp[i][j][u] = min(dp[i][j][u], dp[i - 1][col[i - 1]][u] + w[i][j]); } else { dp[i][j][u + 1] = min(dp[i][j][u + 1], dp[i - 1][col[i - 1]][u] + w[i][j]); } } else { if (j == v) { dp[i][j][u] = min(dp[i][j][u], dp[i - 1][v][u] + w[i][j]); } else { dp[i][j][u + 1] = min(dp[i][j][u + 1], dp[i - 1][v][u] + w[i][j]); } } } } } } long long ans = inf; for (int i = 1; i <= m; i++) { ans = min(ans, dp[n][i][k]); } if (ans >= inf) { cout << "-1" << endl; } else { cout << ans <<endl; } return 0; }