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加值/把第一棵树拉出来单独处理。
#include<cstdio>
#include<cstring>
typedef long long LL;
LL ans[][][];
LL p[][];
LL c[];
LL n,m,k2,minans=0x3f3f3f3f3f3f3f3f;
LL min(LL a,LL b)
{
return a>b?b:a;
}
int main()
{
LL i,j,k,q;
scanf("%I64d%I64d%I64d",&n,&m,&k2);
for(i=;i<=n;i++)
scanf("%I64d",&c[i]);
for(i=;i<=n;i++)
for(j=;j<=m;j++)
scanf("%I64d",&p[i][j]);
memset(ans,0x3f,sizeof(ans));
for(i=;i<=m;i++)
ans[][i][]=;
for(i=;i<=n;i++)
{
if(c[i]==)
{
for(j=;j<=m;j++)
for(k=;k<=k2;k++)
{
ans[i][j][k]=ans[i-][j][k];
for(q=;q<=m;q++)
if(q!=j||i==)
ans[i][j][k]=min(ans[i][j][k],ans[i-][q][k-]);
ans[i][j][k]+=p[i][j];
}
}
else
{
j=c[i];
for(k=;k<=k2;k++)
{
ans[i][j][k]=ans[i-][j][k];
for(q=;q<=m;q++)
if(q!=j||i==)
ans[i][j][k]=min(ans[i][j][k],ans[i-][q][k-]);
}
}
}
for(i=;i<=m;i++)
minans=min(ans[n][i][k2],minans);
if(minans==0x3f3f3f3f3f3f3f3f)
printf("-1");
else
printf("%I64d",minans);
return ;
}