洛谷ac,梦熊爆炸,求卡常
查看原帖
洛谷ac,梦熊爆炸,求卡常
1420772
liangyimim楼主2025/7/24 12:06
#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
int main()
{
	int n;
	cin>>n;
	vector<int> a(n),s(n);
	for(int i=0;i<n;i++) 
	{
		cin>>a[i];
		s[i]=a[i]+(i?s[i-1]:0);
	}
	vector<vector<int>> f(n,vector<int>(n,0));
	for(int i=1;i<n;i++) f[i][i-1]=1;
	for(int i=0;i<n;i++) f[i][i]=1;
	for(int len=2;len<=n;len++)
	{
		for(int l=0;l+len-1<n;l++)
		{
			int r=l+len-1;
			for(int k=l;k<r;k++)
			{
				for(int h=k;h<r;h++)
				{
					int sum1=s[k]-(l?s[l-1]:0);
					int sum2=s[r]-s[h];
					if(f[l][k]&&f[k+1][h]&&f[h+1][r]&&sum1==sum2)
					{
						f[l][r]=1;
					}
				}
			}
		}
	}
	int ans=0;
	for(int l=0;l<n;l++)
	{
		for(int r=l;r<n;r++)
		{
			if(f[l][r])
			{
				ans=max(ans,s[r]-(l?s[l-1]:0));
			}
		}
	}
	cout<<ans;
	return 0;
}
2025/7/24 12:06
加载中...