题目大意
现在Bessie的饱食度为 0 ,她每吃一个橙子,饱食度就会增加 A ;每吃一个柠檬,饱食度就会增加 B 。Bessie还有一次喝水的机会,如果Bessie喝水前饱食度为 x ,喝水后饱食度会变为 ⌊x/2⌋ 。
Bessie的饱食度不能超过 T (1 ≤ T ≤ 5,000,000) ,否则肚子会爆炸。试求Bessie的饱食度最大能达到多少。
题目分析
观察题目,明显可知如果没有喝水这一操作,这就是一道无限背包。
考虑如何处理喝水,我们不妨跑两次无限背包,第一次没有喝水的操作,把能达到的饱食度除以2的值在第二个无限背包中更新一下(相当于喝水)。然后再跑一遍裸无限背包就行。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int MAXN=5e6+10; 4 5 int t,ans; 6 int a[5]; 7 bool f[MAXN][3]; 8 int main(){ 9 scanf("%d%d%d",&t,&a[1],&a[2]); 10 f[0][0]=f[0][1]=1; 11 for(int i=1;i<=2;++i) 12 for(int j=0;j+a[i]<=t;++j) 13 if(f[j][0]){ 14 f[j+a[i]][0]=1; 15 f[(j+a[i])/2][1]=1; 16 ans=max(ans,j+a[i]); 17 } 18 for(int i=1;i<=2;++i) 19 for(int j=0;j+a[i]<=t;++j) 20 if(f[j][1]){ 21 f[j+a[i]][1]=1; 22 ans=max(ans,j+a[i]); 23 } 24 printf("%d\n",ans); 25 return 0; 26 }