题目描述

茜又闯进了农夫约翰的家中！

她在厨房发现了无限多的柠檬和橙子，于是决定饱餐一顿。

每吃一个橙子会增加她的饱腹感 A，每吃一个柠檬会增加她的饱腹感 B。

此外，如果她愿意的话，她还可以喝一次水，喝水可以降低她一半的饱腹感（向下取整）。

出于健康考虑，她的饱腹感不能超过 T。

请确定她能达到的最大饱腹感是多少。

样例

输入格式
共一行包含三个整数 T,A,B。

输出格式
输出她能达到的最大饱腹感。

数据范围
1≤T≤5×106,
1≤A,B≤T。

输入样例：
8 5 6
输出样例：
8

算法1

(暴力枚举) $O(n)$

这个题其实就是一个背包问题，然后我们在做的时候，一般来说我们可以用f[j]表示是否让饱腹度为j,因为题目中加了喝水，这个时候我们可以加一个维度(状态机) ,f[0][j]代表不喝水可以达到的饱腹度，f[1][j]代表喝了水以后可以达到的饱腹度，因为这个只能喝一次水，所以不需要太多的额外判断。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=5000010;
int f[2][N];
int main()
{
    int t,a,b;
    cin>>t>>a>>b;
    f[0][0]=1;
    for(int i=0;i<2;i++)
        for(int j=0;j<=t;j++)
        {
            if(f[i][j]==0)
                continue;
            if(j+a<=t) f[i][j+a]=1;
            if(j+b<=t) f[i][j+b]=1;
            if(i==0)
                f[i+1][j/2]=1;
        }

    while(f[1][t]==0) t--;
    cout<<t;
    return 0;
}