http://poj.org/problem?id=1615
#include"iostream"
#include"stdlib.h"
#include"memory.h"
//#include"time.h"
using namespace std;
long m[5][100],len[5],n,total,answer;
///////////////////////////
long cas;
///////////////////////////
void init()
{
n=5;total=0;
int i,j;
for(i=0;i<n;i++)
{
len[i]=80;
for(j=0;j<len[i];j++)
{
m[i][j]=rand()%201-100;
total+=m[i][j];
}
}
}
void init1()
{
n=0;total=0;
do
{
len[n]=0;
do
{
cin>>m[n][len[n]++];
total+=m[n][len[n]-1];
}
while(m[n][len[n]-1]!=9999&&m[n][len[n]-1]!=-9999);
total-=m[n][len[n]-1];
len[n]--;
n++;
}while(m[n-1][len[n-1]]!=-9999);
}
int a[5];long next;int prev[520];
void find(long sum,long max,int rest)
{
int i;long sa,sb;
if(answer>=0&&max>answer)return;
if(rest==0)
{
answer=max;
return;
}
for(i=0;i<n;i++)
if(a[i]<len[i])
{
if(prev[rest]>=0&&prev[rest]!=i)
{
sa=m[prev[rest]][a[prev[rest]]-2];
if(m[prev[rest]][a[prev[rest]]-1]+m[i][a[i]]>0)sa+=m[prev[rest]][a[prev[rest]]-1]+m[i][a[i]];
sb=m[i][a[i]];
if(m[i][a[i]+1]+m[prev[rest]][a[prev[rest]]-2]>0)sb+=m[i][a[i]+1]+m[prev[rest]][a[prev[rest]]-2];
if(sa>sb)continue;
}
a[i]+=2;
sum+=m[i][a[i]-2];
prev[rest-2]=i;
find(sum+m[i][a[i]-1],sum>max?sum:max,rest-2);
sum-=m[i][a[i]-2];
a[i]-=2;
}
return ;
}
void yasuo()
{
int i,j,k;
for(i=0;i<n;i++)
{
for(j=1,k=0;j<len[i];j++)
{
if(m[i][j]==0)continue;
if((m[i][j]>=0&&m[i][k]>=0)||(m[i][j]<=0&&m[i][k]<=0))m[i][k]+=m[i][j];
else
{
k++;
m[i][k]=m[i][j];
}
}
len[i]=k+1;
if(m[i][k]>0)m[i][len[i]++]=0;
m[i][len[i]]=-9999;
}
return ;
}
int main()
{
int t,i,st;long sum;
cin>>t;
while(t--)
{
init1();
//init();
yasuo();
sum=0;st=0;
for(i=0;i<n;i++)
{
a[i]=0;
if(m[i][0]<=0)
{
a[i]++;
sum+=m[i][0];
}
st+=len[i]-a[i];
}
answer=-1;prev[st]=-1;
find(sum,0,st);
cout<<answer<<endl;
}
return 0;
}