USACO 2015 Dec Gold 2.Fruit Feast

题目描述

Description

Bessie has broken into Farmer John's house again! She has discovered a pile of lemons and a pile of oranges in the kitchen (effectively an unlimited number of each), and she is determined to eat as much as possible.Bessie has a maximum fullness of T (1≤T≤5,000,000). Eating an orange increases her fullness by A, and eating a lemon increases her fullness by B (1≤A,B≤T). Additionally, if she wants, Bessie can drink water at most one time, which will instantly decrease her fullness by half (and will round down).

Help Bessie determine the maximum fullness she can achieve!

Input

The first (and only) line has three integers T, A, and B.

Output

A single integer, representing the maximum fullness Bessie can achieve.

Sample Input

8 5 6

Sample Output

8

题目分析:

SB背包 不解释

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
bool f[5000100];
int n;
int w[3];
int main()
{
    scanf("%d%d%d",&n,&w[1],&w[2]);
    f[0]=1;
    for(int i=1;i<=2;i++)
        for(int j=w[i];j<=n;j++)
            if(f[j-w[i]]) f[j]=1;
    if(f[n]) printf("%d",n);
    else
    {
        for(int i=1;i<=n;i++)
            if(f[i]) f[i>>1]=1;
        for(int i=1;i<=2;i++)
            for(int j=w[i];j<=n;j++)
                if(f[j-w[i]]) f[j]=1;
        for(int i=n;i>=0;i--)
            if(f[i])    
            {
                printf("%d",i);
                return 0;
            }
    }
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注