1005better动划.cpp

平时acm训练时ac的源代码

//1005
#define N 100000
#include<iostream.h>
#include<stdio.h>
#include<math.h>
//#include<malloc.h>
typedef struct p
{
	long br;
	long w;
	int next;
}point;
point node[N]={0};
int cp=0;
point *m[21]={0};
long a[21]={0,4364,165,4413,63,148,4365,43,54,5253,4432,43,2,4343,1232,3232,435,42,42,4261,425};//;//={0,5,8,13,27,14};
point *lp[21]={0},*rp[21]={0};
int v[21]={0};
int total=0;
long inline search(int i,long j)
{
	int flag=0;

	if(lp[i]==NULL)
		lp[i]=m[i];
	

	do
	{
		if(lp[i]->next==0)
		{
			return lp[i]->w;

		}
		else if((lp[i]+1)->br>j)
			return lp[i]->w;
		else
			lp[i]++;
	}while(lp[i]);
}
	
long inline rsearch(int i,long j)
{
	int flag=0;

	if(rp[i]==NULL)
		rp[i]=m[i];
	do
	{
		if(rp[i]->next==0)
		{
			return rp[i]->w;

		}
		else if((rp[i]+1)->br>j)
			return rp[i]->w;
		else
			rp[i]++;
	}while(rp[i]);
}		

inline find(int n,int w)
{
	int i;
	long j;
	long temp,temp2,left=w;
	m[n]=&node[0];
	node[cp].br=0;
	node[cp].w=0;
	node[cp].next=1;
	cp++;
	node[cp].br=a[n];
	node[cp].w=a[n];
	node[cp].next=0;
//	left-=a[i];
	for(i=n-1;i>=1;i--)
	{
		
		
		for(j=0;j<=w;j++)
		{
			if(m[i]==0&&j==0)
			{
				cp++;
				m[i]=node+cp;
				node[cp].br=0;
				node[cp].w=search(i+1,j);
				node[cp].next=0;
				
			}
			else if(j<a[i])
			{
				
				temp=search(i+1,j);
				if(temp>node[cp].w)
				{
					node[cp].next=1;
					cp++;
					node[cp].br=j;
					node[cp].w=temp;
					node[cp].next=0;
				}
			}
			else if(j>=a[i])
			{
				temp=search(i+1,j);
				temp2=(rsearch(i+1,j-a[i])+a[i]);
				if(temp>temp2)
				{
					if(temp>node[cp].w)
					{
						node[cp].next=1;
						cp++;
						node[cp].br=j;
						node[cp].w=temp;
						node[cp].next=0;
					}
				}
				else if(temp2>node[cp].w)
				{	
					{
						node[cp].next=1;
						cp++;
						node[cp].br=j;
						node[cp].w=temp2;
						node[cp].next=0;
					}
				}
			}
		}
	}
					
					


}
long inline tsearch(int i,long j)
{
	int flag=0;
	point *p=m[i];
	int k=0;
	do
	{
		if(p[k].next==0)
			return p[k].w;
		else if(p[k+1].br>j)
			return p[k].w;
		else
			p++;
	}while(p);
}


inline trace(int n,int w)
{
	int i;
	long last=w;
	long temp;
	for(i=1;i<=n-1;i++)
	{
		if(tsearch(i,last)==tsearch(i+1,last))
			v[i]=0;
		else
		{
			v[i]=1;
			last-=a[i];
			total++;
		}
	}
	v[n]=(search(n,last)>0)?1:0;
	
}		


inline qusort(long a[],int n)
{
	int i,j;
	for(i=1;i<=n-1;i++)
		for(j=1;j<=n-i;j++)
		{
			if(a[j]>a[j+1])
			{
				long temp=a[j];
				a[j]=a[j+1];
				a[j+1]=temp;
			}
		}
}

main()
{
	int i,n=15;
	long sum=0;
	long l=0,r=0;
	cin>>n;
	 
	for(i=1;i<=n;i++)
		cin>>a[i];
//	qusort(a,n);
	for(i=1;i<=n;i++)
	{
		sum+=a[i];
	}
	find(n,sum/2);
	for(i=0;i<=20;i++)
	{
		lp[i]=0;
		rp[i]=0;
	}
	trace(n,sum/2);
	
	for(i=1;i<=n;i++)
		if(v[i]==0)
			l+=a[i];
		else
			r+=a[i];
	printf("%ld",abs(r-l));
//	cin>>n;
}