第一次我把初始值设为0x3f,第二次0x3f3f3f3f,第一次40,第二次直接100了,这是为啥啊各位大佬
40pts:
#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:
#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;
}