[DP]美食家

题目：

众所周知小W是个美(chi)食(huo)家。饱度可以用一个整数来表示，小W的最大饱度为W（$W \le 5000000$W≤5000000）。这一天小W来到一家自助餐厅，餐厅里有甲、乙两种菜，小W吃一口甲会获得A点饱度，吃一口乙会获得B点饱度(A,B≤W)，甲乙两道菜都无限量供应。小W还带着一片健胃消食片，可以在任意时刻选择吃下这片健胃消食片。吃下健胃消食片后，小W的饱度会立刻减半（向下取整）。整个过程中，如果某一时刻小W的饱度超过W，小W就会非常难受，因此小W绝对不会让自己的饱度超过W。现在小W想知道他能达到的最大饱度是多少?

分析：

看到题目第一眼我认为直接输出W，因为无论A和B是多少最大的都会是 $W$W ，事实证明我太天真了QAQ

如果直接输出W，那么下面这个数据就过不掉：

输入

177 122 123

输出

123

所以肯定要换一种思路。

可以先打一遍暴搜，然后就可以发现，对于任意的 $W$W ：

• 如果上一次没吃健胃消食片，则可能从 $W-a$W−a ，$W-b$W−b 转移过来。

• 如果上一次吃过健胃消食片：

  • 如果正好是上一次吃了健胃消食片，则可能从 $2 \times W$2×W ，$2 \times W+1$2×W+1 转移过来。

  • 如果上一次之前吃过健胃消食片，则可能从 $W-a$W−a ，$W-b$W−b 转移过来。

搜索肯定会超时（废话），所以对于上面的发现，可以用动态规划解决。又因为 $W \le 5000000$W≤5000000 ，所以只能开bool数组。

设 $f[w][1/0]$f[w][1/0] 表示饱度为 $w$w ，吃或没吃过健胃消食片的情况下，饱度能不能达到 $w$w 。

初始化：$f[0][0]=f[0][1]=true$f[0][0]=f[0][1]=true

则：

• 如果上一次没吃健胃消食片，则：

  $w \ge a:f[w][0]=f[w][0]||f[w-a][0]$w≥a:f[w][0]=f[w][0]∣∣f[w−a][0]
  $w \ge b:f[w][0]=f[w][0]||f[w-b][0]$w≥b:f[w][0]=f[w][0]∣∣f[w−b][0]

• 如果上一次吃过健胃消食片：

  • 如果正好是上一次吃了健胃消食片，则：

    $2 \times w \le W:f[w][1]=f[w][1]||f[2 \times w][0]$2×w≤W:f[w][1]=f[w][1]∣∣f[2×w][0]
    $2 \times w+1 \le W:f[w][1]=f[w][1]||f[2 \times w+1][0]$2×w+1≤W:f[w][1]=f[w][1]∣∣f[2×w+1][0]

  • 如果上一次之前吃过健胃消食片，则：

    $w \ge a:f[w][1]=f[w][1]||f[w-a][1]$w≥a:f[w][1]=f[w][1]∣∣f[w−a][1]
    $w \ge b:f[w][1]=f[w][1]||f[w-b][1]$w≥b:f[w][1]=f[w][1]∣∣f[w−b][1]

注意：必须先处理 $f[w][0]$f[w][0] 再处理 $f[w][1]$f[w][1] ，因为同时处理的话 $f[w][1]$f[w][1] 可能会用到 $f[2 \times w][0]$f[2×w][0] 或 $f[2 \times w+1][0]$f[2×w+1][0] 的值，而这两项都没有处理到。

最后从 $w$w 开始倒序枚举，如果 $f[i][0]$f[i][0] 或 $f[i][1]$f[i][1] 为true，则直接输出 $i$i 。

代码：

#include <cstdio>
bool f[5000003][2];
int main(){
    int w,a,b;scanf("%d%d%d",&w,&a,&b);
    f[0][0]=f[0][1]=1;//初始化
    for(int i=1;i<=w;i++){//先处理f[i][0]的情况
        if(i>=a) f[i][0]|=f[i-a][0];
        if(i>=b) f[i][0]|=f[i-b][0];
    }
    for(int i=1;i<=w;i++){//再处理f[i][1]的情况
        if((i<<1)<=w) f[i][1]|=f[i<<1][0];
        if((i<<1)+1<=w) f[i][1]|=f[(i<<1)+1][0];
        if(i>=a) f[i][1]|=f[i-a][1];
        if(i>=b) f[i][1]|=f[i-b][1];
    }
    for(int i=w;i>=1;i--)//从w到1枚举
        if(f[i][0]||f[i][1])
        	return printf("%d\n",i),0;
}