Coloring Trees CodeForces - 711C

Coloring Trees CodeForces - 711C

題意：有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 }