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 编辑 ]

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

没

看来我还得重新再考虑

估计还是的用贪婪算法，前不久刚学完动态规划，贪婪刚接触，有时候会把他们弄混，我相信不久就可以解决（如果有高人也可指点一二，自己学不易）

2013年4月27日竞赛题目
小H是一个程序员。但是他很喜欢一些新奇的东西。

有一次，他去找物理实验室的朋友玩。他见到了一串非常有意思的粒子。N个粒子排成一排。每一秒中，每一段连续的粒子中会随意有一个爆炸，爆炸后该粒子就消失了，且将原来连续的一段粒子分隔成两段。

小H希望知道所有粒子都爆炸完的期望时间。

Input

         第一行为一个整数T（1 <= T<= 400），表示有T组测试数据；

         每组数据一个正整数N（1<=N<=400），表示一开始的粒子数。

Output

         对于每组数据，输出期望时间（秒）。保留五位小数。

Sample Input
3
1
2
3
 
Sample Output
1.00000
2.00000
2.66667
 
Sample Cl.
对N=3，若第一个爆炸的粒子在旁边，则还需两秒；若第一个爆炸的在中间，则再过一秒即可。故答案为2/3*3+1/3*2=8/3。

在贴一道，

#include<stdio.h>
double qiwang(int n)
{
double q=0.00000;
int j;
if(1==n)
  return 1.00000;
else if(2==n)
  return 2.00000;
else
{
  if(n%2==0)
  {
   for(j=n;j>n/2;j--)
   q+=(1.0/n)*2*(qiwang(j-1)+1);
   return q;

  }
  else
  {
   for(j=n;j>n/2;j--)
   q+=(1.0/n)*2*(qiwang(j-1)+1);
   q=q-1.0/n*(qiwang(j)+1);
   return q;
  }

 

}
}
void main()
{
int t,n[400],i;
scanf("%d",&t);
for(i=0;i<t;i++)
scanf("%d",&n[i]);
for(i=0;i<t;i++)
printf("%f\n",qiwang(n[i]));
}
都说效率不高