https://cn.vjudge.net/contest/245857#problem/C

代码：

#include<iostream>

#include<string>

#include<queue>

#include<cmath>

#include<stack>

#include<vector>

#include<map>

#include<algorithm>

#include<stdio.h>

#include<cstring>

using namespace std;

# define ll  long long

const ll  LL_INF=0x3f3f3f3f3f3f3f3f;

# define maxn 100+10

ll a[maxn][maxn];

ll dp[maxn][maxn][maxn];

ll tr[maxn];

void init()

{

    memset(a,LL_INF,sizeof(a));

    memset(dp,LL_INF,sizeof(dp));

    memset(tr,LL_INF,sizeof(tr));

}

int main()

{

    ll n,m,k;

    while(cin>>n>>m>>k)//n代表树的个数，m代表的是颜料的种类，k代表的是需要划分成多少段

    {

        init();

        for(int i=1; i<=m; i++)

        {

            dp[0][0][i]=0;

        }

        for(int i=1; i<=n; i++)

        {

            cin>>tr[i];//记录树的原始状态

            // if(tr[i]==0)flag=1;

        }

        for(int i=1; i<=n; i++)

        {

            for(int j=1; j<=m; j++)

            {

                cin>>a[i][j];

                if(tr[i])a[i][tr[i]]=0;

            }

        }

        for(int i=1; i<=n; i++)//dp【i】【j】【k】，i代表第几棵树，j代表当前树是划分区间的第几段，w代表的是当前这一段用什么颜料

        {

            for(int j=1; j<=k&&j<=i; j++)

            {

                for(int w=1; w<=m; w++)

                {

                    if(tr[i]&&tr[i]!=w)continue;

                    ll minn=LL_INF;

                    for(int l=1; l<=m; l++)

                    {

                        if(l==w)continue;

                        minn=min(minn,dp[i-1][j-1][l]);

                    }

                    if(i>=2)

                        dp[i][j][w]=min(dp[i-1][j][w],minn)+a[i][w];

                    else if(i==1)dp[i][j][w]=a[i][w];

                    // cout<<dp[i][j][w]<<endl;

                }

            }

        }

        // cout<<y<<endl;{

        ll minn=LL_INF;

        for(int i=1; i<=m; i++)

        {

            // cout<<dp[n][k][i]<<endl;

            minn=min(minn,dp[n][k][i]);

        }

        if(minn==LL_INF)cout<<-1<<endl;

        else

            cout<<minn<<endl;

        //  }

    }

    return 0;

}