社区讨论
代码比样例最小值多了1 qwq,大佬路过求助指点,谢谢!
P1880[NOI1995] 石子合并参与者 3已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @lod2f8i6
- 此快照首次捕获于
- 2023/10/30 23:39 2 年前
- 此快照最后确认于
- 2023/11/05 09:57 2 年前
CPP
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
int N,a[100010],sum[100010],f_Max[2010][2010],f_Min[2010][2010];
int main()
{
scanf("%d",&N);
for(int i=1;i<=N;i++)
{
scanf("%d",&a[i]);
a[i+N]=a[i];
}
for(int i=1;i<=2*N;i++)
sum[i]=sum[i-1]+a[i];
memset(f_Min,0x3f3f,sizeof(f_Min));
for(int i=1;i<=N;i++)
f_Min[i][i]=0;
for(int len=2;len<=N;len++)
{
for(int i=1;i<=2*N-len+1;i++)
{
int j=i+len-1;
for(int k=i;k<j;k++)
{
f_Max[i][j]=max(f_Max[i][j],f_Max[i][k]+f_Max[k+1][j]+sum[j]-sum[i-1]);
f_Min[i][j]=min(f_Min[i][j],f_Min[i][k]+f_Min[k+1][j]+sum[j]-sum[i-1]);
}
}
}
int Minn=0x3f3f,Maxn=-9999999;
for(int i=1;i<=N;i++)
{
Minn=min(Minn,f_Min[i][i+N-1]);
Maxn=max(Maxn,f_Max[i][i+N-1]);
}
printf("%d\n%d",Minn,Maxn);
return 0;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...