自动搬运

查看原文

来自洛谷，原作者为

	qscweadzx **

搬运于2025-08-24 22:04:15，当前版本为作者最后更新于2019-02-27 12:51:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这可能是最像NOIP初赛题的题解……

基本思路：多重背包+特别处理喝水的情况+多重背包

具体实现参见代码

#include <bits/stdc++.h>
using namespace std;
bool f[5000100]={1};//由于题目只需要判断可否达到饱食度，故不需要开int类型
int a,b,t;
int main(){
    cin>>t>>a>>b;
    for(int i=a;i<=t;++i)f[i]|=f[i-a];//多重背包，若i-a饱食度可达到，则i饱食度可达到（位运算其实只是显得秀）
    for(int i=b;i<=t;++i)f[i]|=f[i-b];//同上，多重背包
    for(int i=1;i<=t;++i)f[i>>1]|=f[i];//喝水，如果i饱食度可达到，则i/2饱食度可达到
    for(int i=a;i<=t;++i)f[i]|=f[i-a];//喝完水后再次多重背包
    for(int i=b;i<=t;++i)f[i]|=f[i-b];
    while(!f[t])--t;//从饱食度最高值向低枚举
    cout<<t<<endl;
    return 0;
}

求过审……