Coloring Trees CodeForces

题意：有n个点，每个点有一个c值，如果为0表示它没有被染色，否则表示它被染成了c值的颜色。颜色有1到m。把第i棵树染成颜色j所需要的代价是p[i][j]。求最小的代价，使得将每棵树都染色，且如果将连续的一串同色的树视为一个集合，共有k个集合。输出代价，如果不可能达到要求输出-1。

方法：

$ans[i][j][k]$表示把前i棵树染好，并且最后一种颜色是j，并且总共有k段的最小费用。

首先初始化ans全部值为一个很大的树（方便min），然后$ans[0][1..m][0]=0$

c[i]=0时：更新每个j

$ans[i][j][k]=min(ans[i-1][j][k]+p[i][j],min{ans[i-1][q][k-1]+p[i][j] | 1<=q<=m})$

也就是$ans[i][j][k]=min(ans[i-1][j][k],min{ans[i-1][q][k-1] | 1<=q<=m})+p[i][j]$

c[i]=1时：只更新$j=c[i]$
$ans[i][j][k]=min(ans[i-1][j][k],min{ans[i-1][q][k-1] | 1<=q<=m})$

注意：i=1也就是第一棵树需要特判。可以在循环里加条件/在0加值/把第一棵树拉出来单独处理。

 1 #include<cstdio>
 2 #include<cstring>
 3 typedef long long LL;
 4 LL ans[101][101][101];
 5 LL p[101][101];
 6 LL c[101];
 7 LL n,m,k2,minans=0x3f3f3f3f3f3f3f3f;
 8 LL min(LL a,LL b)
 9 {
10     return a>b?b:a;
11 }
12 int main()
13 {
14     LL i,j,k,q;
15     scanf("%I64d%I64d%I64d",&n,&m,&k2);
16     for(i=1;i<=n;i++)
17         scanf("%I64d",&c[i]);
18     for(i=1;i<=n;i++)
19         for(j=1;j<=m;j++)
20             scanf("%I64d",&p[i][j]);
21     memset(ans,0x3f,sizeof(ans));
22     for(i=1;i<=m;i++)
23         ans[0][i][0]=0;
24     for(i=1;i<=n;i++)
25     {
26         if(c[i]==0)
27         {
28             for(j=1;j<=m;j++)
29                 for(k=1;k<=k2;k++)
30                 {
31                     ans[i][j][k]=ans[i-1][j][k];
32                     for(q=1;q<=m;q++)
33                         if(q!=j||i==1)
34                             ans[i][j][k]=min(ans[i][j][k],ans[i-1][q][k-1]);
35                     ans[i][j][k]+=p[i][j];
36                 }
37         }
38         else
39         {
40             j=c[i];
41             for(k=1;k<=k2;k++)
42             {
43                 ans[i][j][k]=ans[i-1][j][k];
44                 for(q=1;q<=m;q++)
45                     if(q!=j||i==1)
46                         ans[i][j][k]=min(ans[i][j][k],ans[i-1][q][k-1]);
47             }
48         }
49     }
50     for(i=1;i<=m;i++)
51         minans=min(ans[n][i][k2],minans);
52     if(minans==0x3f3f3f3f3f3f3f3f)
53         printf("-1");
54     else
55         printf("%I64d",minans);
56     return 0;
57 }