2847273_ac_0ms_1112k.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#define inf -210000000

struct node
{
	int w, b;
}team[1001];

int dp[1001][16][16];
int n;

int max(int b,int c)
{
	return b>c?b:c;
}

int main()
{
	int a;
	int i, b, w;
	int p, s, t;

	n = 1;
	while(scanf("%d%d",&a,&b)==2)
	{
		team[n].w = a;
		team[n].b = b;
		n++;
	}
	memset(dp,0,sizeof(dp));
	for(i = 1; i < n; i++)
	{
		for(w = 0; w <= 15; w++)
		{
			for(b = 0; b <= 15; b++)
			{
				if(i<w+b)
				{
					dp[i][w][b] = inf;
					continue;
				}
				if(!w&&!b)
				{
					dp[i][w][b] = 0;
					continue;
				}
				p = dp[i-1][w][b];
				if(w)
					s = dp[i-1][w-1][b]+team[i].w;
				else
					s = inf;
				if(b)
					t = dp[i-1][w][b-1]+team[i].b;
				else
					t = inf;
				dp[i][w][b] = max(p,max(s,t));
			}
		}
	}
	printf("%d\n",dp[n-1][15][15]);
	return 0;
}