现在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 }
USACO 2015 December Contest Gold T2: Fruit Feast
原文：https://www.cnblogs.com/LI-dox/p/11215649.html