萌新求助!最小值一直不对
查看原帖
萌新求助!最小值一直不对
256815
ji_guang楼主2021/11/15 14:15

求求大佬们帮忙看看哪里有问题

#include<bits/stdc++.h>
using namespace std;
const int N=205;
int dp1[N][N],dp2[N][N]={0},max1=0,min1=0x3f3f3f,n,z[N],s[N]={0};
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>z[i];
		z[i+n]=z[i];
	}
	for(int i=1;i<=n+n;i++)
	{
		s[i]=s[i-1]+z[i];
	}
	for(int len=1;len<n;len++)
	{
		for(int j=1;j+len<n+n;j++)
		{
			int ends=j+len;
			dp2[j][ends]=0x3f3f3f;
			for(int i=j;i<ends;i++)
			{
				dp2[j][ends]=min(dp2[j][ends],dp2[j][i]+dp2[i+1][ends]+s[ends]-s[j-1]);
				dp1[j][ends]=max(dp1[j][ends],dp1[j][i]+dp1[i+1][ends]+s[ends]-s[j-1]);
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		max1=max(max1,dp1[i][i+n-1]);
		min1=min(min1,dp1[i][i+n-1]);
	}
	cout<<min1<<endl<<max1;
}
2021/11/15 14:15
加载中...