1615.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#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;
}