2017NOIP 问题 C: 墙壁 需要60-100程序

Question

60分的程序帮忙一下，100分也行
如果需要题解可以问我拿(我看不懂)

Answer 1

以下回复参考：皆我百晓生、券券喵儿等免费微信小程序作答:

解析： 这是一个动态规划问题，需要求解在给定条件下的最小代价。我们可以使用三维数组dp[i][j][c]来表示当前绚丽值为i，j号砖块颜色为c的最小代价。在状态转移时，我们需要枚举位置j-1的颜色t，然后更新dp[i][j][c]的值。

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 405, M = 405, K = 405;
const int INF = 1e9 + 7;

int n, m, k;
int p[N][M];
int C[N];
int dp[N][N][M];

int main() {
    freopen("wall.in", "r", stdin);
    freopen("wall.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &C[i]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &p[i][j]);

    memset(dp, 0x3f, sizeof(dp));
    for (int i = 1; i <= m; i++) dp[0][0][i] = 0;

    for (int w = 1; w <= k; w++) {
        for (int j = 1; j <= n; j++) {
            int c = C[j];
            if (c == 0) {
                for (int t = 1; t <= m; t++) {
                    for (int pre_w = max(0, w - 1); pre_w <= min(k, w + 1); pre_w++) {
                        dp[w][j][t] = min(dp[w][j][t], dp[pre_w][j - 1][t] + p[j][t]);
                    }
                }
            } else {
                dp[w][j][c] = min(dp[w][j][c], dp[w][j - 1][c]);
            }
        }
    }

    int ans = INF;
    for (int i = 1; i <= m; i++) ans = min(ans, dp[k][n][i]);
    if (ans >= INF) ans = -1;
    printf("%d
", ans);
    return 0;
}

注意：这段代码需要在Windows系统下运行，如果需要输出long long类型，请使用%I64d。