社区讨论
求助不能用INT32_MAX,能用0x3f3f3f3f的原因
P1436棋盘分割参与者 2已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @lo141hhc
- 此快照首次捕获于
- 2023/10/22 14:51 2 年前
- 此快照最后确认于
- 2023/11/02 14:22 2 年前
代码如下,第38行把INF改成INT32_MAX后,ans会变成很大的负数?但是dp计算过程跟ans没有关系吧......不理解为什么
CPP#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int val[10][10] = {0};
int dp[20][10][10][10][10] = {0}; // n i j k l
int get_val_sq(int i, int j, int k, int l) {
int x = val[k][l] - val[k][j - 1] - val[i - 1][l] + val[i - 1][j - 1];
return x * x;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= 8; i++) {
for (int j = 1; j <= 8; j++) {
cin >> val[i][j];
val[i][j] += val[i - 1][j] + val[i][j - 1] - val[i - 1][j - 1];
}
}
for (int i = 1; i <= 8; i++) {
for (int j = 1; j <= 8; j++) {
for (int k = i; k <= 8; k++) {
for (int l = j; l <= 8; l++) {
// initialize
dp[1][i][j][k][l] = get_val_sq(i, j, k, l);
}
}
}
}
for (int t = 2; t <= n; t++) {
for (int i = 1; i <= 8; i++) {
for (int j = 1; j <= 8; j++) {
for (int k = i; k <= 8; k++) {
for (int l = j; l <= 8; l++) {
int ans = INF;
// cut in line
for (int c = j; c < l; c++) {
int val1 = dp[1][i][j][k][c] + dp[t - 1][i][c + 1][k][l];
int val2 = dp[t - 1][i][j][k][c] + dp[1][i][c + 1][k][l];
ans = min(ans, min(val1, val2));
}
// cut in row
for (int c = i; c < k; c++) {
int val1 = dp[1][i][j][c][l] + dp[t - 1][c + 1][j][k][l];
int val2 = dp[t - 1][i][j][c][l] + dp[1][c + 1][j][k][l];
ans = min(ans, min(val1, val2));
}
dp[t][i][j][k][l] = ans;
}
}
}
}
}
cout << dp[n][1][1][8][8] << endl;
return 0;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...