社区讨论

求助不能用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 条回复,欢迎继续交流。

正在加载回复...