Coloring Trees CodeForces

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

分享

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         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 }

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台