【henuacm2016级暑期训练-动态规划专题 B】Coloring Trees

在这里输入题意

【题解】

f[i][j][k]前i个位置,第i个位置放j这个颜色,然后形成了k个联通块的最小花费
分第i个位置有没有已经放颜色两种情况考虑。
如果有放的话。枚举前一个位置的颜色以及前i-1个位置形成的联通块的数目
如果没有放的话。枚举当前以及前一个的颜色以及前i-1个位置形成的联通块数目
有放不用加代价。
没有放的话加上放的代价就会。

最后在f[n][1..m][k]里面找最小值

【代码】

#include <bits/stdc++.h>

using namespace std;

const int N = 100;

int n,m,k,c[N+10],p[N+10][N+10];

long long f[N+10][N+10][N+10];

void get_min(long long &x,long long y){

    if (x==-1) x = y;

    if (y<x) x = y;

}

int main()

{

    #ifdef LOCAL_DEFINE

        freopen("D:\\rush.txt","r",stdin);

    #endif // LOCAL_DEFINE

    ios::sync_with_stdio(0),cin.tie(0);

    cin >> n >> m>>k;

    for (int i = 1;i <= n;i++) cin >> c[i];

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

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

            cin >> p[i][j];

    memset(f,255,sizeof f);

    f[0][0][0] = 0;

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

        if (c[i]!=0){

            //第i个位置的颜色已经固定。

            //枚举前一个的颜色

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

                for (int k = 0;k <= i-1;k++)

                    if (f[i-1][j][k]!=-1){

                        if (j!=c[i]){

                            get_min(f[i][c[i]][k+1],f[i-1][j][k]);

                        }else{

                            get_min(f[i][c[i]][k],f[i-1][j][k]);

                        }

                    }

        }else{

            //这一个的颜色和前一个的颜色都要枚举

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

                for (int jj = 0;jj <= m;jj++)

                    for (int k = 0;k <= i-1;k++){

                        if (f[i-1][jj][k]!=-1){

                            if (j!=jj){

                                get_min(f[i][j][k+1],f[i-1][jj][k]+p[i][j]);

                            }else{

                                get_min(f[i][j][k],f[i-1][jj][k]+p[i][j]);

                            }

                        }

                    }

        }

    }

    //f[n][1..m][k]

    long long ans = -1;

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

        if (f[n][i][k]!=-1)

            get_min(ans,f[n][i][k]);

    cout<<ans<<endl;

    return 0;

}

巴特西

【henuacm2016级暑期训练-动态规划专题 B】Coloring Trees

最新文章

热门文章