CF711C Coloring Trees（dp）

根据数据范围，可以看出能够看出可以构建三维dp状态为前i个分为k段当前是j色，之后按情况更新

#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
#include<algorithm>
#define ull unsigned long long
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll f[102][102][102];
ll p[110][110];
int c[110];
int main(){
    int n,m,k;
    cin>>n>>m>>k;
    int i;
    for(i=1;i<=n;i++){
        cin>>c[i];
    }
    int j;
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            cin>>p[i][j];
        }
    }
    memset(f,0x3f,sizeof f);
    if(c[1]==0){
        for(i=1;i<=m;i++){
            f[1][i][1]=p[1][i];
        }
    }
    else
        f[1][c[1]][1]=0;
    ll tmp=1e18;
    int l;
    int r;
    for(i=2;i<=n;i++){
        for(j=1;j<=k;j++){
            if(j>i)
                break;
            if(c[i]!=0){
                for(l=1;l<=m;l++){
                    if(l==c[i]){
                        f[i][l][j]=min(f[i][l][j],f[i-1][l][j]);
                    }
                    else{
                        f[i][c[i]][j]=min(f[i][c[i]][j],f[i-1][l][j-1]);
                    }
                }
            }
            else{
                for(l=1;l<=m;l++){
                    for(r=1;r<=m;r++){
                        if(l==r)
                            f[i][l][j]=min(f[i][l][j],f[i-1][r][j]+p[i][l]);
                        else
                            f[i][l][j]=min(f[i][l][j],f[i-1][r][j-1]+p[i][l]);
                    }

                }
            }
        }
    }
    ll ans=1e18;
    if(c[n]){
        ans=f[n][c[n]][k];
    }
    else{
       for(i=1;i<=m;i++){
        ans=min(ans,f[n][i][k]);
    }
    }
    if(ans>=1e18/2)
        cout<<-1<<endl;
    else
        cout<<ans<<endl;
}