bzoj4393[Usaco2015 Dec]Fruit Feast*

bzoj4393[Usaco2015 Dec]Fruit Feast

题意：

奶牛一开始饱胀值为0，上限为T。每个柠檬派提供a点饱胀值，每个橘子派提供b点饱胀值，有一次机会喝水，使得饱胀值div2。柠檬派和橘子派有无限个，求最大饱胀值。T≤5000000。

题解：

dfs。f[i][1/0]表示当前饱胀值为i，是/否喝过水的状态能否达到。则由f[i][1]可递推出f[i+a][1]、f[i+b][1]，由f[i][0]可递推出f[i+a][0]、f[i+b][0]、f[i/2][1]。

代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define inc(i,j,k) for(int i=j;i<=k;i++)
 5 #define maxn 5000010
 6 using namespace std;
 7 
 8 bool vis[maxn][2]; int n,a,b,ans;
 9 void dfs(int x,int y){
10     if(vis[x][y])return; vis[x][y]=1; if(x+a<=n)dfs(x+a,y); if(x+b<=n)dfs(x+b,y);
11     if(!y)dfs(x/2,1); ans=max(ans,x);
12 }
13 int main(){
14     scanf("%d%d%d",&n,&a,&b); memset(vis,0,sizeof(vis)); dfs(0,0); printf("%d",ans); return 0;
15 }

20160908