A了,但有疑问!!!!!!!!!
查看原帖
A了,但有疑问!!!!!!!!!
846041
__xxy_free_ioi__楼主2024/12/19 19:25

这是有问题的代码:

#include <bits/stdc++.h>

using namespace std;

const int N = 210;

int n;
int a[N], f[N][N], g[N][N], s[N];

int main() {
    cin >> n;
    memset(f, 0x3f, sizeof f);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i + n] = a[i];
        f[i][i] = 0;
    }
    for (int i = 1; i <= 2 * n; i++) {
        s[i] = s[i - 1] + a[i];
    }
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= 2 * n; i++) {
            int j = i + len - 1;
            for (int k = i; k < j; k++) {
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
                g[i][j] = max(g[i][j], g[i][k] + g[k + 1][j] + s[j] - s[i - 1]);
            }
        }
    }
    int mnans = 1e9, mxans = 0;
    for (int i = 1; i + n - 1 <= 2 * n; i++) {
        int j = i + n - 1;
        mnans = min(mnans, f[i][j]);
        mxans = max(mxans, g[i][j]);
    }
    cout << mnans << '\n' << mxans;
    return 0;
}

就非常神奇,一开始我敲完代码之后发现有问题,想了半天也没有想到为什么会错,后面一看之前写的代码,发现只要动动我们神秘的小指头,将代码改成下面这样,他就会AC,但我想了半天也不知道为啥(O_o)??

    cin >> n;
    // memset(f, 0x3f, sizeof f);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i + n] = a[i];
    }
    for (int i = 1; i <= 2 * n; i++) {
        s[i] = s[i - 1] + a[i];
    }
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= 2 * n; i++) {
            int j = i + len - 1;
            f[i][j] = 1e9;
            for (int k = i; k < j; k++) {
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
                g[i][j] = max(g[i][j], g[i][k] + g[k + 1][j] + s[j] - s[i - 1]);
            }
        }
    }
    int mnans = 1e9, mxans = 0;
    for (int i = 1; i + n - 1 <= 2 * n; i++) {
        int j = i + n - 1;
        mnans = min(mnans, f[i][j]);
        mxans = max(mxans, g[i][j]);
    }
    cout << mnans << '\n' << mxans;

有木有dalao帮我看一看为什么

2024/12/19 19:25
加载中...