平衡秤.txt

包括计算几何、特殊数据结构、组合数学等知识点的代码。每个代码对应一道ACM试题

#include <iostream>
#include <string>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

//平衡秤 动态规划 NOJ 1023
//类似背包问题，注意只用2个一维空间就可存放状态

#define MAX 5000002
#define NMAX 105
long f[2][MAX];//f[i][j] 前i个数，数之和的一半为j的情况下所能取到的最大数之和
long a[NMAX];

long cal(long geshu,long max)
{
	long i,j;
	memset(f,0,sizeof(f));
	for(i=1;i<=geshu;i++)
	{
		for(j=1;j<=max;j++)
		{
			if(j-a[i]>=0) 
			{	//可以放入第i个数
				//两种情况讨论
				if(f[(i-1)%2][j]<=f[(i-1)%2][j-a[i]]+a[i])
					//如果放入第i个数，所放数的和增加a[i],不过前i-1个数所限定的和要相应减少
					f[i%2][j]=f[(i-1)%2][j-a[i]]+a[i];
				else f[i%2][j]=f[(i-1)%2][j];
			}
			else //放不下第i个数	
				f[i%2][j]=f[(i-1)%2][j];
		}
	}
	return f[geshu%2][max];
}

int main()
{
	long num,i,sum,answer,j=0;
	while(scanf("%ld",&num)!=EOF)
	{
		sum=0;
		j++;
		for(i=1;i<=num;i++)
		{
			scanf("%ld",&a[i]);
			sum+=a[i];
		}
		answer=cal(num,sum/2);
		cout<<"Case "<<j<<": "<<answer<<" "<<sum-answer<<endl;
	}
	return 0;
}