Codeforces Round #369 (Div. 2) C. Coloring Trees 数位dp，好题

Source

Codeforces Round #369 (Div. 2)

My Solution

数位dp， 好题

状态定义 dp i j k 为 当前在 从左往右 第 i 位， 且 以 j 结尾， 已经有 k 个片段

初始化  dp[ i ][ j ][ k ] = INF

边界 if(i == 1) ......

状态转移方程 if(val[ i ] == 0)  dp[ i ][ j ][ k ] = min(dp[ i ][ j ][ k ], dp[ i - 1 ][ x ][ k - 1] + p[ i ][ j ]);     // x = 1 ~ m, x != j

else  dp[ i ][ j ][ k ] = min(dp[ i ][ j ][ k ], dp[ i - 1][ x ][ k - 1]);     // x = 1 ~ m, x != j

复杂度 O(n^4)

#include 
#include 
#include 

using namespace std;
typedef long long LL;
const int maxn = 1e2 + 8;


LL col[maxn], p[maxn][maxn], dp[maxn][maxn][maxn];

int main()
{
    #ifdef LOCAL
    freopen("c.txt", "r", stdin);
    //freopen("o.txt", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);


    LL n, m, kk;
    cin >> n >> m >> kk;
    for(int i = 1; i <= n; i++){ cin >> col[i];
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){ cin >> p[i][j];
        }
    }

    for(int i = 0; i <= n + 1; i++){
        for(int  j = 0; j <= m + 1; j++){
            for(int k = 0; k <= kk + 1; k++){
                dp[i][j][k] = 9e18;
            }
        }
    }
    //cout<<dp[0][0][0]<<endl;

    int i, j, k, y;
    for(i = 1; i <= n; i++){
        for(k = 1; k <= kk; k++){ if(k > i) break;
            if(col[i] != 0){
                if(i == 1){
                    dp[i][col[i]][1] = 0;
                    continue;
                }
                j = col[i];
                dp[i][j][k] = dp[i-1][j][k];
                for(y = 1; y <= m; y++){
                    if(j == y) continue;
                    else dp[i][j][k] = min(dp[i][j][k], dp[i - 1][y][k - 1]);
                }
            }
            else{
                if(i == 1){
                    for(y = 1; y <= m; y++){
                        dp[i][y][1] = p[1][y];
                    }
                    continue;
                }

                for(j = 1; j <= m; j++){
                    dp[i][j][k] = dp[i - 1][j][k] + p[i][j];
                    for(y = 1; y <= m; y++){
                        if(j == y) continue;
                        else dp[i][j][k] = min(dp[i][j][k], dp[i - 1][y][k - 1] + p[i][j]);
                    }
                }
            }
        }
    }


    LL ans = 9e18;
    for(j = 1; j <= m; j++){
        ans = min(ans, dp[n][j][kk]);
    }
    if(ans == 9e18) cout << -1 << endl;
    else cout << ans << endl;


    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx