社区讨论
我好像是按着环做的吧 但最小值还是44 求助dalao
P1880[NOI1995] 石子合并参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mi7vzdim
- 此快照首次捕获于
- 2025/11/21 04:31 4 个月前
- 此快照最后确认于
- 2025/11/21 04:31 4 个月前
CPP
#include <iostream>
#include <algorithm>
#include <numeric>
using namespace std;
const int INF=24000100;
int n,a[220],s[220];
int fmax[220][220],fmin[220][220];
int main(){
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i];
a[i+n]=a[i];
}
partial_sum(a+1,a+1+2*n,s+1);
for(int i=1;i<=2*n-1;++i){
fmax[i][i+1]=a[i]+a[i+1];
fmin[i][i+1]=a[i]+a[i+1];
}
for(int d=2;d<=n-1;++d)
for(int i=1,j;(j=i+d)<=2*n;++i){
fmin[i][j]=INF;
for(int k=i;k<j;++k){
fmax[i][j]=max(fmax[i][j],fmax[i][k]+fmax[k+1][j]+s[j]-s[i-1]);
fmin[i][j]=min(fmin[i][j],fmin[i][k]+fmin[k+1][j]+s[j]-s[i-1]);
}
}
cout<<fmin[1][n]<<endl<<fmax[1][n];
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...