比赛 csp2025模拟练习2 评测结果 AAAWAAWTATTTEEE
题目名称 Chocolate Bar Partition 最终得分 40
用户昵称 梦那边的美好TE 运行时间 16.612 s
代码语言 C++ 内存使用 15.95 MiB
提交时间 2025-10-29 11:29:08
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=2005;
int n,s,a[3][N],f[N][N],val,len,sum[3][N];
bool check(int l,int r,int L,int R){
	if(l>r){
		if(2ll*(sum[2][R]-sum[2][L-1])*n==1ll*s*(R-L+1))return 1;
		else return 0;
	}
	if(L>R){
		if(2ll*(sum[1][r]-sum[1][l-1])*n==1ll*s*(r-l+1))return 1;
		else return 0;
	}
	if(R<l||r<L)return 0;
	val=sum[1][r]-sum[1][l-1]+sum[2][R]-sum[2][L-1];
	len=r-l+1+R-L+1;
	if(2ll*val*n==1ll*s*len)return 1;
	else return 0;	
}
int dfs(int x,int y){
	if(x==0&&y==0)return 0;
	if(f[x][y]!=0x3f3f3f3f)return f[x][y];
	int res=-1e9;
	for(int a=0;a<x;a++){
		if(check(a+1,x,y+1,y))res=max(res,dfs(a,y)+1);
	}
	for(int b=0;b<y;b++){
		if(check(x+1,x,b+1,y))res=max(res,dfs(x,b)+1);
	}
	for(int a=0;a<x;a++){
		for(int b=0;b<y;b++){
			if(check(a+1,x,b+1,y)){
				res=max(res,dfs(a,b)+1);
			}
		}
	} 
	return f[x][y]=res;
}
int main(){
	freopen("Chocolate.in","r",stdin);
	freopen("Chocolate.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",a[1]+i);
		sum[1][i]=sum[1][i-1]+a[1][i];
		s+=a[1][i];
	}
	for(int i=1;i<=n;i++){
		scanf("%d",a[2]+i);
		sum[2][i]=sum[2][i-1]+a[2][i];
		s+=a[2][i];
	}
	memset(f,0x3f,sizeof(f));
	printf("%d\n",dfs(n,n));
	return 0;
}