pku 1015 最小差最大和.txt

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

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <iterator>
using namespace std;
//PKU 1015
/*
4 2 
1 2 
2 3 
4 1 
6 2 
0 0 
*/
#define NMAX 202
#define MMAX 852
#define XMAX 22
#define PB push_back
typedef struct man
{
	bool f;//是否存在
	int sum;//和
	vector <int> a;//哪些人被选中
}man;

int p[NMAX];
int d[NMAX];
man state[2][XMAX][MMAX];//man[i][j][k]，从前i个人里选j个人，k=p[]-d[]+400;

int max(int a,int b)
{
	if(a>b) return a;
	else return b;
}

bool cmp(int a,int b)
{
	return a<b;
}

void cal(int nnum,int mnum)
{
	int i,j,k,mmin,mmax,tt,pre,now,smax,tk,ps,ds,t,choose;
	int cha[NMAX];
	vector<int>::iterator iter;
	for(i=0;i<=1;i++)
	{
		for(j=0;j<XMAX;j++)
		{
			for(k=0;k<MMAX;k++)
			{
				state[i][j][k].f=false;
				state[i][j][k].sum=0;
				state[i][j][k].a.clear();
			}
		}
	}

	for(i=1;i<=nnum;i++)
		cha[i]=p[i]-d[i];
	sort(cha+1,cha+1+nnum,cmp);
	tt=0;
	for(i=1;i<=mnum;i++) tt+=cha[i];
	mmin=tt;
	tt=0;
	for(i=nnum;i>nnum-mnum;i--) tt+=cha[i];
	mmax=tt;
	for(i=1;i<=nnum;i++)
		cha[i]=p[i]-d[i];

	pre=1;
	now=0;
	state[0][1][cha[1]+400].f=true;
	state[0][1][cha[1]+400].sum=p[1]+d[1];
	state[0][1][cha[1]+400].a.PB(1);
	state[0][0][400].f=true;
	state[1][0][400].f=true;
	for(i=2;i<=nnum;i++)
	{
		now=pre;
		pre=(pre+1)%2;
		for(j=1;j<=mnum && j<=i;j++)
		{
			for(k=0;k<=800;k++)
			{
				if(state[pre][j][k].f==true ||(k-cha[i]>=0 &&state[pre][j-1][k-cha[i]].f==true))
				{	//如果不选第i个人，选前面j个人，或选第i个人，选前面j-1人的情况成立
					state[now][j][k].f=true;
					if((state[pre][j][k].f==true && state[pre][j-1][k-cha[i]].f==true && state[pre][j][k].sum>=state[pre][j-1][k-cha[i]].sum+p[i]+d[i] )|| (state[pre][j][k].f==true && state[pre][j-1][k-cha[i]].f==false))
					{	//选第i个人，选前面j-1人的这种情况不成立，或这种情况成立但不合算
						state[now][j][k].sum=state[pre][j][k].sum;
						choose=1;
					}
					else 
					{
						state[now][j][k].sum=state[pre][j-1][k-cha[i]].sum+p[i]+d[i];
						choose=2;
					}
					if(choose==2)
					{
						state[now][j][k].a=state[pre][j-1][k-cha[i]].a;
						state[now][j][k].a.PB(i);
					}
					else 
						state[now][j][k].a=state[pre][j][k].a;
				}		
			}
		}
	}
	tt=10000;
	smax=0;
	for(k=mmin+400;k<=mmax+400;k++)
	{
		if((tt>abs(k-400) && state[now][mnum][k].f==true)|| ( tt==abs(k-400) && smax<state[now][mnum][k].sum))
		{
			tt=abs(k-400);
			smax=state[now][mnum][k].sum;
			tk=k;
		}
	}
	ps=ds=0;
	for(iter=state[now][mnum][tk].a.begin();iter!=state[now][mnum][tk].a.end();iter++)
	{
		ps+=p[*iter];
		ds+=d[*iter];
	}
	printf("Best jury has value %d for prosecution and value %d for defence: \n",ps,ds);
	for(iter=state[now][mnum][tk].a.begin();iter!=state[now][mnum][tk].a.end();iter++)
	{
		printf("%d ",*iter);
	}

}

int main()
{
	int nnum,mnum,ii=0,i,psum=0,dsum=0;
	scanf("%d %d",&nnum,&mnum);
	while(!(nnum==0 && mnum==0))
	{
		for(i=1;i<=nnum;i++)
		{
			scanf("%d %d",&p[i],&d[i]);
		}
		printf("Jury #%d\n",++ii);
		cal(nnum,mnum);
		printf("\n\n");
		scanf("%d %d",&nnum,&mnum);
	}
	return 0;
}