2576.txt

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

Problem Id:2576  User Id:fzk 
Memory:4488K  Time:671MS
Language:C++  Result:Accepted

Source 

#include"iostream.h"
#include"math.h"
char a[101][45010];
int main()
{
 int b[101];
	long n,i,j,k,h,w;long s;
	
	while(1)
	{cin>>n;s=0;
	if(cin.fail())break;
    for(i=1;i<=n;i++)
	for(j=0;j<=n*450;j++)a[i][j]=0;
		a[0][0]=1;
		for(k=0;k<n;k++){cin>>b[k];s+=b[k];}

  for(k=0;k<n;k++)
  {h=k>n/2?n/2:k;
  w=b[k]; 
  
  for(i=h;i>=0;i--)
   for(j=0;j<=i*450;j++)
	   if(a[i][j]&&!a[i+1][j+w]){a[i+1][j+w]=1;}
	}	
	
  long t=0;
	
	for(h=0;h<n/2*450;h++)
	{if(a[n/2][h]&&abs(2*h-s)<abs(2*t-s))t=h;}
 
	
 	if(2*t>s)t=s-t;
	cout<<t<<' '<<s-t<<endl;
	}

return 1;
}