为啥初始值设定不一样,分数不一样啊,求助各位大佬
  • 板块学术版
  • 楼主Lunar_Whisper
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/3/1 22:27
  • 上次更新2024/3/2 09:52:44
查看原帖
为啥初始值设定不一样,分数不一样啊,求助各位大佬
968531
Lunar_Whisper楼主2024/3/1 22:27

第一次我把初始值设为0x3f0x3f,第二次0x3f3f3f3f0x3f3f3f3f,第一次40,第二次直接100了,这是为啥啊各位大佬

40pts40pts:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int>c(n + 110);
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
    }
    vector<vector<int>>p(n + 110, vector<int>(m + 110));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> p[i][j];
        }
    }
    vector<vector<vector<long long>>>dp(n + 110, vector<vector<long long>>(m + 110, vector<long long>(k + 110, 0x3f)));
    if (c[1] == 0) {
        for (int i = 1; i <= m; i++) {
            dp[1][i][1] = p[1][i];
        }
    } else dp[1][c[1]][1] = 0;
    for (int i = 1; i < n; i++) {
        for (int k1 = 1; k1 <= k; k1++) {
            if (c[i]) {
                if (c[i + 1]) {
                    dp[i + 1][c[i + 1]][k1 + (c[i + 1] != c[i])] = min(dp[i + 1][c[i + 1]][k1 + (c[i + 1] != c[i])], dp[i][c[i]][k1]);
                } else {
                    for (int j = 1; j <= m; j++) {
                        dp[i + 1][j][k1 + (j != c[i])] = min(dp[i][c[i]][k1] + p[i + 1][j], dp[i + 1][j][k1 + (j != c[i])]);
                    }
                }
            } else {
                for (int j = 1; j <= m; j++) {
                    if (c[i + 1]) {
                        dp[i + 1][c[i + 1]][k1 + (j != c[i + 1])] = min(dp[i + 1][c[i + 1]][k1 + (j != c[i + 1])], dp[i][j][k1]);
                    } else {
                        for (int l = 1; l <= m; l++) {
                            dp[i + 1][l][k1 + (j != l)] = min(dp[i + 1][l][k1 + (j != l)], dp[i][j][k1] + p[i + 1][l]);
                        }
                    }
                }
            }
        }
    }
    long long ret = 0x3f;
    for (int i = 1; i <= m; i++) {
        ret = min(ret, dp[n][i][k]);
    }
    if (ret == 0x3f)cout << -1;
    else cout << ret;
    return 0;
}

100pts:100pts:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int>c(n + 110);
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
    }
    vector<vector<int>>p(n + 110, vector<int>(m + 110));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> p[i][j];
        }
    }
    vector<vector<vector<long long>>>dp(n + 110, vector<vector<long long>>(m + 110, vector<long long>(k + 110, 0x3f3f3f3f3f)));
    if (c[1] == 0) {
        for (int i = 1; i <= m; i++) {
            dp[1][i][1] = p[1][i];
        }
    } else dp[1][c[1]][1] = 0;
    for (int i = 1; i < n; i++) {
        for (int k1 = 1; k1 <= k; k1++) {
            if (c[i]) {
                if (c[i + 1]) {
                    dp[i + 1][c[i + 1]][k1 + (c[i + 1] != c[i])] = min(dp[i + 1][c[i + 1]][k1 + (c[i + 1] != c[i])], dp[i][c[i]][k1]);
                } else {
                    for (int j = 1; j <= m; j++) {
                        dp[i + 1][j][k1 + (j != c[i])] = min(dp[i][c[i]][k1] + p[i + 1][j], dp[i + 1][j][k1 + (j != c[i])]);
                    }
                }
            } else {
                for (int j = 1; j <= m; j++) {
                    if (c[i + 1]) {
                        dp[i + 1][c[i + 1]][k1 + (j != c[i + 1])] = min(dp[i + 1][c[i + 1]][k1 + (j != c[i + 1])], dp[i][j][k1]);
                    } else {
                        for (int l = 1; l <= m; l++) {
                            dp[i + 1][l][k1 + (j != l)] = min(dp[i + 1][l][k1 + (j != l)], dp[i][j][k1] + p[i + 1][l]);
                        }
                    }
                }
            }
        }
    }
    long long ret = 0x3f3f3f3f3f;
    for (int i = 1; i <= m; i++) {
        ret = min(ret, dp[n][i][k]);
    }
    if (ret == 0x3f3f3f3f3f)cout << -1;
    else cout << ret;
    return 0;
}
2024/3/1 22:27
加载中...