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

qscweadzx · 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;
}

求过审……