【2012百度之星/初赛下】C:度度熊的礼物

描述：度度熊拥有一个自己的Baidu空间，度度熊时不时会给空间朋友赠送礼物，以增加度度熊与朋友之间的友谊值。度度熊在偶然的机会下得到了两种超级礼物，于是决定给每位朋友赠送一件超级礼物。不同类型的朋友在收到不同的礼物所能达到的开心值是不一样的。开心值衡量标准是这样的：每种超级礼物都拥有两个属性(A, B)，每个朋友也有两种属性(X, Y)，如果该朋友收到这个超级礼物，则这个朋友得到的开心值为A*X + B*Y。
由于拥有超级礼物的个数限制，度度熊很好奇如何分配这些超级礼物，才能使好友的开心值总和最大呢？

输入

第一行n表示度度熊的好友个数。

接下来n行每行两个整数表示度度熊好朋友的两种属性值Xi, Yi。

接下来2行，每行三个整数k_i, A_i, B_i，表示度度熊拥有第i种超级礼物的个数以及两个属性值。

1<=n<=1000, 0<=X_i,Y_i, A_i, B_i 1+k₂>=n

输出

输出一行一个值表示好友开心值总和的最大值

样例输入

4

3 6

7 4

1 5

2 4

3 3 4

3 4 3

样例输出

118

提示

送给第一种礼物的人有1，3，4，送给第二种礼物的人有2

代码1：

#include<iostream>
#include<algorithm>
using namespace std;
int f[1001];
struct node
{
	int x , y;
}human[1001];
int num1,num2,a1,b1,a2,b2;

int main(void)
{
	int n , i , j , ans;
	scanf("%d",&n);
	for(i = 1 ; i <= n ; ++i)
		scanf("%d %d" , &human[i].x , &human[i].y);
	scanf("%d %d %d" , &num1 , &a1 , &b1);
	scanf("%d %d %d" , &num2 , &a2 , &b2);

	memset(f,-1,sizeof(f));
	//printf("%d\n",f[1]);
	ans = -1000000;
	f[0] = 0;
	for(i = 1 ; i <= min(n,num2) ; ++i)
		f[i] = f[i-1] + human[i].x*a2 + human[i].y*b2;
	if(f[n] > ans)
		ans = f[n];
	//f[0]=human[1].a*a1+human[1].b*b1;
	//printf("ans:%d\n",ans);
	for(i = 1 ; i <= min(num1,n) ; ++i)
	{
		f[0] = f[0] + human[i].x*a1 + human[i].y*b1;
		//printf("i:%d j:0 f:%d\n",i,f[0]);
		for(j = 1 ; j <= min(n-i,num2) ; ++j)
		{
			f[j] = max(f[j-1]+human[i+j].x*a2+human[i+j].y*b2 , f[j]+human[i+j].x*a1+human[i+j].y*b1);
			//printf("i:%d j:%d f:%d\n",i,j,f[j]);
		}
		if(f[n-i] > ans)
			ans = f[n-i];
	}
	printf("%d\n",ans);
	return 0;
}

代码2：

#include<iostream>
using namespace std;

int c[1000][2000];

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

int main(void)
{
    int i , j , t , n , k1 , k2 , a1 , a2 , b1 , b2 , max;
    int x[1001] , y[1001];
    cin >> n;
    for (i = 1 ; i <= n ; ++i)
        cin >> x[i] >> y[i];
    cin >> k1 >> a1 >> b1 >> k2 >> a2 >> b2;

	t = maxx(x[1]*a1+y[1]*b1,x[1]*a2+y[1]*b2);
    c[1][k1+k2] = x[1]*a1+y[1]*b1;
    c[1][0] = x[1]*a2+y[1]*b2;
    for(i = 1 ; i <= k1+k2-1 ; ++i)
        c[1][i] = t;
    for(j = 2 ; j <= n ; ++j)
    {
        for(i = 0 ; i <= k1+k2-j+1 ; ++i)
            c[j][i] = maxx(c[j-1][i+1]+x[j]*a1+y[j]*b1,c[j-1][i]+x[j]*a2+y[j]*b2);
    }
	max = 0;
    for(i = 0 ; i <= k1+k2-n+1 ; ++i)
    {
        if(c[n][i] > max)
            max = c[n][i];
    }
    cout << max << endl;
    return 0;
}

DP方法：

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 1002; 
int x[MAXN], y[MAXN], dp[MAXN][MAXN], a[3], b[3], k[3]; 

int main(void)
{
	int n , i , j , ans , c1 ,c2;
	while(scanf("%d", &n) != EOF)
	{
		for (i = 1; i <= n; ++i)
		{
			scanf("%d %d", &x[i], &y[i]);
		}
		for (i = 1; i <= 2; ++i)
		{
			scanf("%d %d %d", &k[i], &a[i], &b[i]);
		}
		memset(dp , 0 , sizeof(dp));
		for (i = 1; i <= n; ++i)
		{
			for (j = 0; j <= k[1] && j <= i; ++j)
			{
				if (i - j > k[2])
					continue;
				c1 = a[1] * x[i] + b[1] * y[i] ;
				c2 = a[2] * x[i] + b[2] * y[i] ;
				if(j)
					dp[i][j] = dp[i - 1][j - 1] + c1;
				if(i - j)
					dp[i][j] = max(dp[i][j], dp[i - 1][j] + c2);
			}
		}
		ans = 0;
		for (i = 0; i <= k[1]; ++i)
			ans = max(ans, dp[n][i]);
		printf("%d\n", ans);
	}
	return 0;
}