USACO 2015 December Contest Gold T2: Fruit Feast

题目大意

现在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 2016 US Open Contest Gold T1: Splitting the Field


下一篇:USACO 2005 December Gold - Layout (差分约束)