社区讨论

代码比样例最小值多了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 条回复,欢迎继续交流。

正在加载回复...