这是有问题的代码:
#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帮我看一看为什么