题解 P4817 【[USACO15DEC]Fruit Feast 水果盛宴】

· · 题解

思路：枚举

枚举各种可能状态，用ans更新答案

水题，直接上代码

#include <cstdio>
#include <algorithm>
using namespace std;
bool b[5000001][2];||记录状态 
int T,A,B,ans;
void dfs(int x,int flag)||flag记录是否喝过水
{
    if(b[x][flag])
        return; ||已经枚举过该状态，返回（不判断状态会超时三个点，如我）
    b[x][flag]=1; 
    if(x+A<=T)
        dfs(x+A,flag); ||吃橙子不会撑爆，吃一个
    if(x+B<=T)
        dfs(x+B,flag);||吃柠檬不会撑爆，吃一个
    if(!flag)||没喝过水，喝一口
        dfs(x/2,1); 
    ans=max(ans,x);||更新答案
}
int main()
{
    scanf("%d %d %d",&T,&A,&B); 
    dfs(0,0); 
    printf("%d",ans); 
    return 0;
}

蒟蒻第一次发题解，欢迎大佬帮忙指正