# Coloring Trees CodeForces

2017-09-14 08:05:35来源:cnblogs.com作者:711C - hehe_54321人点击

Coloring Trees CodeForces - 711C

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

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/})\$

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/})\$

` 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         else39         {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     else55         printf("%I64d",minans);56     return 0;57 }`