60分,TLE 4个点。码风有点屎,望见谅
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<stack>
#include<queue>
using namespace std;
const int N=50;
int a[N],b[N],c[N],d[N];
int s1,s2,s3,s4;
int lbrain,rbrain,res,minn;
void dfs(int s,int kemu,int last)
{
if(kemu==1)
{
if(s>s1)
{
minn=min(minn,max(lbrain,rbrain));
return;
}
for(int i=last+1;i<=s1;i++)
{
lbrain+=a[i];
dfs(s+1,kemu,i);
lbrain-=a[i];
rbrain+=a[i];
dfs(s+1,kemu,i);
rbrain-=a[i];
}
}else if(kemu==2){
if(s>s2)
{
minn=min(minn,max(lbrain,rbrain));
return;
}
for(int i=last+1;i<=s2;i++)
{
lbrain+=b[i];
dfs(s+1,kemu,i);
lbrain-=b[i];
rbrain+=b[i];
dfs(s+1,kemu,i);
rbrain-=b[i];
}
}else if(kemu==3){
if(s>s3)
{
minn=min(minn,max(lbrain,rbrain));
return;
}
for(int i=last+1;i<=s3;i++)
{
lbrain+=c[i];
dfs(s+1,kemu,i);
lbrain-=c[i];
rbrain+=c[i];
dfs(s+1,kemu,i);
rbrain-=c[i];
}
}else{
if(s>s4)
{
minn=min(minn,max(lbrain,rbrain));
return;
}
for(int i=last+1;i<=s4;i++)
{
lbrain+=d[i];
dfs(s+1,kemu,i);
lbrain-=d[i];
rbrain+=d[i];
dfs(s+1,kemu,i);
rbrain-=d[i];
}
}
}
int main()
{
cin>>s1>>s2>>s3>>s4;
for(int i=1;i<=s1;i++) cin>>a[i];
lbrain=rbrain=0;
minn=0x3f3f3f3f;
dfs(1,1,0);
//cout<<minn<<" ";
res+=minn;
for(int i=1;i<=s2;i++) cin>>b[i];
lbrain=rbrain=0;
minn=0x3f3f3f3f;
dfs(1,2,0);
//cout<<minn<<" ";
res+=minn;
for(int i=1;i<=s3;i++) cin>>c[i];
lbrain=rbrain=0;
minn=0x3f3f3f3f;
dfs(1,3,0);
//cout<<minn<<" ";
res+=minn;
for(int i=1;i<=s4;i++) cin>>d[i];
lbrain=rbrain=0;
minn=0x3f3f3f3f;
dfs(1,4,0);
//cout<<minn<<endl;
res+=minn;
cout<<res<<endl;
return 0;
}