傳送門
石子合并
AC代碼
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int a[210], f[210][210], sum[210], f2[210][210];
int main(){
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
a[n+i] = a[i];
sum[i] = sum[i-1] + a[i];
}
for(int i = n+1; i <= n+n; i++){
sum[i] = sum[i-1] + a[i];
}
for(int len = 1; len <= n; len++){
for(int i = 1, j = i + len; (j <= n+n) && i <= n+n; i++ , j = i+len){
f2[i][j] = 0x3f3f3f;
for(int k = i; k < j; k++){
// cout << sum[j] - sum[i-1] << endl;
f[i][j] = max(f[i][j], f[i][k]+f[k+1][j]+sum[j] - sum[i-1]);
f2[i][j] = min(f2[i][j], f2[i][k]+f2[k+1][j]+ sum[j] - sum[i-1]);
}
}
}
int maxn = -1;
for(int i = 1; i <= n; i++){
maxn = max(maxn, f[i][i+n-1]);
}
int minn = 0x3f3f3f;
for(int i = 1; i <= n; i++){
minn = min(minn, f2[i][i+n-1]);
}
cout << minn << endl;
cout << maxn << endl;
return 0;
}
