2.    度度熊拥有一个自己的Baidu空间，度度熊时不时会给空间朋友赠送礼物，以增加度度熊与朋友之间的友谊值。度度熊在偶然的机会下得到了两种超级礼物，于是决定给每位朋友赠送一件超级礼物。不同类型的朋友在收到不同的礼物所能达到的开心值是不一样的。开心值衡量标准是这样的：每种超级礼物都拥有两个属性(A, B)，每个朋友也有两种属性(X, Y)，如果该朋友收到这个超级礼物，则这个朋友得到的开心值为A*X + B*Y。
由于拥有超级礼物的个数限制，度度熊很好奇如何分配这些超级礼物，才能使好友的开心值总和最大呢？
3.    输入
4.    第一行n表示度度熊的好友个数。
5.    接下来n行每行两个整数表示度度熊好朋友的两种属性值Xi, Yi。
6.    接下来2行，每行三个整数ki, Ai, Bi，表示度度熊拥有第i种超级礼物的个数以及两个属性值。
7.    1<=n<=1000, 0<=Xi,Yi, Ai, Bi 1+k2>=n
8.    输出
9.    输出一行一个值表示好友开心值总和的最大值
10.  样例输入
11.  4
12.  3 6
13.  7 4
14.  1 5
15.  2 4
16.  3 3 4
17.  3 4 3
18.  样例输出
19.  118
20.  提示
21.  送给第一种礼物的人有1，3，4，送给第二种礼物的人有2

闲逛是发现的，拿过来大家探讨一下，
不知还有其它更好的算法吗
以下是我做的：
#include<stdio.h>
void main()
{
        int n,x[50+1],y[50+1],a[2+1],b[2+1],c[50+1],i,n1[3];    //x[i]表示第i个人的x属性值,y[i]表示第i个人的y属性值;c[i]表示i个人的最大开心值
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        scanf("%d %d",&x[i],&y[i]);
        for(i=1;i<=2;i++)
                scanf("%d %d %d",&n1[i],&a[i],&b[i]);
        if(x[1]*a[1]+y[1]*b[1]>x[1]*a[2]+y[1]*b[2])
                c[1]=x[1]*a[1]+y[1]*b[1];
        else
                c[1]=x[1]*a[2]+y[1]*b[2];
        
        for(i=2;i<=n;i++)
        {
if(x[i]*a[1]+y[i]*b[1]>x[i]*a[2]+y[i]*b[2])
c[i]=c[i-1]+x[i]*a[1]+y[i]*b[1];
else
c[i]=c[i-1]+x[i]*a[2]+y[i]*b[2];

        }
        
printf("%d\n",c[n]);
}

动态规划问题
以上没有考虑礼物个数，只需加限制条件即可，



[ 本帖最后由 heishu 于 2013-4-20 16:26 编辑 ]

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

这是?

就是他的最大值是，第一个人，第三个人，第四个人都拿第一种礼物，第二个人拿第二种礼物

没

呃，小鼠，你这代码跟题目要求相去甚远，还是加上那你认为“即可”的限制条件再讨论的好。

至于原题，你说动态规划我不能说你错，但在我看来叫他它贪心更合适。

目测该题我能构造的最好算法的时间复杂度是O（n*log（n））。

看来我还得重新再考虑

呵呵...写了个，也不知道对不对...找不到验证的地址，学算法也没多长时间...既然是探讨就把代码附上吧...

#include <stdio.h>

int main() {
    int m, a[1100], b[1100], n[5], x[5], y[5], i, j, e, c, d, g, h;
    while(scanf("%d", &m) != EOF) {
        for(i = 1; i <= m; i++) scanf("%d%d", &a[i], &b[i]);
        for(i = 1; i <= 2; i++) scanf("%d%d%d", &n[i], &x[i], &y[i]);
        for(i = 1, e = 0, g = 0, h = 0; i <= m; i++) {
            c = a[i] * x[1] + b[i] * y[1];
            d = a[i] * x[2] + b[i] * y[2];
            if(g <= n[1] && h <= n[2]) {//这里好像有bug
                e += c > d ? c : d;
                c > d ? g++ : h++;
            }
            else e += c > d ? d : c
        }
        printf("%d\n", e);
    }
    return 0;
}
//另外我的第二种比较麻烦的思路是：
将每种结果保存起来，再进行排序，再将满足礼物数量的前提下将最大的加起来得到结果...

 

下面是我的第二种思路，效率不怎么高，见笑了

#include <stdio.h>
void swap(int *a, int *b) {int temp = *a; *a = *b; *b = temp;}
int main() {
    int m, a[1100], b[1100], n[5], x[5], y[5], i, j, e, c[1100], d[1100], k, t;
    while(scanf("%d", &m) != EOF) {
        for(i = 1; i <= m; i++) scanf("%d%d", &a[i], &b[i]);
        for(i = 1; i <= 2; i++) scanf("%d%d%d", &n[i], &x[i], &y[i]);
        for(i = 1; i <= m; i++) {
            c[i] = a[i] * x[1] + b[i] * y[1];
            d[i] = a[i] * x[2] + b[i] * y[2];
        }
        for(i = 1; i <= m; i++)
            for(j = 1; j <= m - i; j++) {
                if(c[j] < c[j + 1]) swap(&c[j], &c[j + 1]);
                if(d[j] < d[j + 1]) swap(&d[j], &d[j + 1]);
            }
        t = n[1] < n[2] ? n[1] : n[2]; e = 0;
        if(t <= m) {
            for(j = 1; j <= t; j++) e += (c[j] > d[j] ? c[j] : d[j]);
            for(k = t + 1; k <= m; k++) e += (c[k] > d[k] ? c[k] : d[k]);
        }
        else for(j = 1; j <= m; j++) e += (c[j] > d[j] ? c[j] : d[j]);
        printf("%d\n", e);
    }
    return 0;
}

这两段代码都不对。再好好想想。