CodeForces

1.求达到某个状态的最小值，考虑用动态规划方式求解。

2.考虑第i棵树的决策，他的颜色对答案及状态的贡献受两个因素的影响：

①上一颗树颜色的选取

②考虑前i-1棵树已经分成了几段

定义dp[i][j][k] ：第i棵树当涂j颜色分成k段时的最小消耗是多少

如果已经涂上色了 dp[i][j][k] = min(dp[i-1][j][k], dp[i-1][w!=j][k-1])

如果没有涂上色 dp[i][j][k] = min(dp[i-1][j][k], dp[i-1][w!=j][k-1] + cost[i][j] ---->实现比较考代码能力

注意初始化

dp把i= 1作为开始点 i=0作为原始点给i=0初始化让它的状态传递到下一个状态

dp[0][0][0] = 0----->因为不存在0树所以成本为0

其余memset(dp, INF, sizeof(dp))

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string>
 4 #include <string.h>
 5 #include <map>
 6 #include <fstream>
 7 #include <set>
 8 #define MAXC 107
 9 #define INF 1e15+7 //最开始0x6f6f6f6f 在test12挂了 说明肯定是大数爆了  INF 设小了
10 #define READ() freopen("in.txt", "r", stdin);
11 using namespace std;
12 typedef long long ll;
13 int n, m, k;
14 int color[MAXC];
15 ll cost[MAXC][MAXC];
16 ll dp[MAXC][MAXC][MAXC];
17 
18 ll solve()
19 {
20     for (int i = 0; i <= n; i++)
21     {
22         for (int j = 0; j <= m; j++)
23         {
24             for (int l = 0  ; l <= k; l++)
25             {
26                 dp[i][j][l] = INF;
27             }
28         }
29     }
30     dp[0][0][0] = 0;
31     for (int i = 1; i <= n; i++)
32     {
33         if (color[i] != 0)
34         {
35             for (int l = 1; l<= k; l++)
36             {
37                 dp[i][color[i]][l] = min(dp[i][color[i]][l], dp[i-1][color[i]][l]);//和i-1同一个色
38                 ll minn = INF;
39                 for (int z = 0; z <= m; z++)//--->>要从dp[0][0][0] 状态转出来
40                 {
41                     if (z != color[i]) minn = min(minn, dp[i-1][z][l-1]);//跟前i-1种不同色 前i-1种有l-1组
42                 }
43                 dp[i][color[i]][l] = min(dp[i][color[i]][l], minn);
44             }
45 
46         }
47         else
48         {
49             for (int l = 1; l <= k; l++)
50             {
51                 for (int j = 1; j <= m; j++)
52                 {
53                     dp[i][j][l] = min(dp[i][j][l], dp[i-1][j][l]) + cost[i][j];//涂一样
54                     ll minn = INF;
55                     for (int z = 0; z <= m; z++)
56                     {
57                         if (z != j) minn = min(minn, dp[i-1][z][l-1]);
58                     }
59                     dp[i][j][l] = min(dp[i][j][l], minn + cost[i][j]);
60                 }
61             }
62         }
63     }
64     ll res = INF;
65     for (int j = 1; j <=m; j++)
66     {
67         res = min(res, dp[n][j][k]);
68     }
69     return res;
70 }
71 
72 
73 int main()
74 {
75     READ()
76     scanf("%d%d%d",&n, &m, &k);
77     for (int i = 1; i <= n; i++)
78     {
79         int c;
80         scanf("%d", &c);
81         color[i] = c;
82     }
83     for (int i = 1; i <= n; i++)
84     {
85         for (int j = 1; j <= m; j++)
86         {
87             scanf("%lld", &cost[i][j]);
88         }
89     }
90     ll ans = solve();
91     if (ans == INF) cout << -1 << endl;
92     else cout << ans << endl;
93 }

对dp的一点小总结

dp的特征数据不是很大求解最优值并要在每一步做出决策

如果纯搜复杂度m^n次

但是dp得好处在于有信息的传递 ---> 对信息的压缩

考虑的这一点就比较容易得出思路确定有几个维度

j-1 告诉 j 颜色用什么 -->显然需要一个颜色维度

k-1 告诉 k已经分成了多少段 --> 显然需要对段数记录的维度

当然第几棵树做什么决策也需要对第几棵树记录可以用之前的数组的重复利用节省内存

也可以添加 i维度记录第几棵树