首页 > 代码库 > bzoj4393[Usaco2015 Dec]Fruit Feast*
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
bzoj4393[Usaco2015 Dec]Fruit Feast*
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。