CodeForces 711C.Coloring Trees【DP】

看上去就是DP的一个题，由于自己太菜了，还是不会做

先给个提交的地方：cf 711C

这个题看到数据，很明显是dp，因为n，m，k的值都不大，我们可以建立矩阵来推理

很明显答案跟dp【n】【k】有关

也就是dp【i】【j】代表前i个树涂完之后，有了j个匹配的最小花费

但是，这样怎么转移呢？！

很明显，数组还可以再开得大一点，多加一维（又相当于多了一个分层图）

dp【i】【j】代表前i个树涂完之后，有了j个匹配，最后一棵树（第i颗树）的颜色为k，的最小花费

那么初始值：

看第一课树是不是染色已经染好了

如果a【i】=0，那么就是需要染色

那么就需要枚举第三维的K，给一个初值

如果a【i】！=0，那么就是不需要染色

那么，那就是dp【1】【1】【a【i】】=0

其他的都是不合法状态

然后状态转移也是根据a【i】是否染色来判断

枚举i，j，k，然后去暴力的计算每个状态量的值

多一维变量枚举，就是说明，如果我想涂的颜色和当前最后一个一样，那么我就需要把美丽度+1

否则是不变的

注意好转移的细节就好

#include<bits/stdc++.h>
using namespace std;

#define LL __int64
LL dp[110][110][110];
LL p[200][200];
int a[200];
const LL INF=0x3f3f3f3f3f3f3f3f3f;

int main(){
    //freopen("input.txt","r",stdin);
    int n,m,k;
    while(scanf("%d%d%d",&n,&m,&k)!=EOF){
        //printf("%d %d %d\n",n,m,k);
        memset(dp,0x3f3f3f3f,sizeof(dp));
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%I64d",&p[i][j]);
        if (a[1]) dp[1][1][a[1]]=0;
        else{
            for(int c=1;c<=m;c++)
                dp[1][1][c]=p[1][c];
        }
        for(int i=2;i<=n;i++)
        if (a[i]==0){
            for(int x=1;x<i;x++)
            for(int c=1;c<=m;c++)
            for(int l=1;l<=m;l++)
                if (l!=c)
                    dp[i][x+1][c]=min(dp[i][x+1][c],dp[i-1][x][l]+p[i][c]);
                else
                    dp[i][x][c]=min(dp[i][x][c],dp[i-1][x][l]+p[i][c]);
        }
        else{
            for(int x=1;x<i;x++)
            for(int l=1;l<=m;l++)
                if (l!=a[i])
                    dp[i][x+1][a[i]]=min(dp[i][x+1][a[i]],dp[i-1][x][l]);
                else
                    dp[i][x][a[i]]=min(dp[i][x][a[i]],dp[i-1][x][l]);
        }
        LL ans=INF;
        for(int c=1;c<=m;c++)
            ans=min(ans,dp[n][k][c]);
        if (ans==INF) ans=-1;
        cout<<ans<<endl;
    }
    return 0;
}