Posted on 2010-07-30 17:01
Onway 阅读(238)
评论(0) 编辑 收藏 引用 所属分类:
伤不起的ACM
pku 2063 容量可变的完全背包
题意:
某人有一大笔资金s(s<1000000),想通过购买债券获利。现有n(n<=10)种债券可买。已知每种债券购买金额w(1000的倍数)和一年后的获利v(不多于购买金额的10%)。可以将每年得到的所有获利都再次投入。问t(t<=40)年后,该人共有多少钱。
看懂题目的第一感觉是没思路,在网上找别的完全背包,找不到了,只能去想这个题。
当时的第一思路是每年获利后都做一次完全背包。至于状态压缩,是将原有资金和购买金额都除以1000,获利不变。每次背包后,都将最大获利除以1000,加到原有资金里(用double型)。
过了样例,提交返回了多次RE。看discuss说数组开小了。为了验证的却是数组越界的错误,一下狠心数组开大了两个数量级。
这下不是RE了,是WA。还是PKU比HDU厚道一点,数组访问越界是报RE,不是WA。
我觉得我是完全看懂了题意,是跟着题意写的代码,而且一次过了样例,这说明思路没错啊。在这种情况下,是可以少测别的数据吧,最多就是测一下边界数组。而直觉告诉我,边界是没问题的。
我怀疑状态压缩出乱子了(没试过压缩的),就干脆不压了,每次RE后都加大数组,一直到MLE。然后编译选错,又来了几个CE。盼星星盼月亮就是盼不到一个AC。
上网查看别人的代码,发现思路跟我的好像不一样。而且都不像我那样,用到double型。我也去掉double类型,将获利先加到总金额,在除以1000赋值给整形。这下提交终于看到AC了。
虽然AC了,但还是有三个地方是不懂得。
1,为什么数组要开到46000呢。
假设将所有资金都能获得最大获利,那么40年后,就是:
1 000 000*(1.1^40)=45259255.568175951805889356034897
2,为什么我用double的时候会出错呢?
其实现在还是不懂,估计也就是有精度损失。
3,别人的思路为什么只求一次完全背包,就的了呢?
由于可以知道40年后的最大金额,不超过46000(压缩后),一次背包后,就能得出每一金额的最大获利。然后每一年获利后都加进去,直接提取出来就可以再次求获利。
1#include <iostream>
2#include <algorithm>
3using namespace std;
4const int MAX=46000;
5int dp[MAX],w[12],v[12];
6int fmax(int a,int b)
7{return a>b?a:b;}
8int main()
9{
10 int t;
11 scanf("%d",&t);
12 while(t--)
13 {
14 int money,year,bond,i,j,sum;
15 scanf("%d%d%d",&money,&year,&bond);
16 for(i=1;i<=bond;++i)
17 {
18 scanf("%d%d",&w[i],&v[i]);
19 w[i]/=1000;
20 }
21
22 memset(dp,0,sizeof(dp));
23 for(i=1;i<=bond;++i)
24 for(j=w[i];j<=MAX-1;++j)
25 dp[j]=fmax(dp[j],dp[j-w[i]]+v[i]);
26
27 while(year--)
28 {
29 sum=money/1000;
30 money+=dp[sum];
31 }
32 printf("%d\n",money);
33 }
34 return 0;
35}