显示代码纯文本
#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;
}