NC24029. [USACO 2015 Dec G]Fruit Feast
描述
Bessie has a maximum fullness of T (1≤T≤5,000,0001≤T≤5,000,000). Eating an orange increases her fullness by A, and eating a lemon increases her fullness by B (1≤A,B≤T1≤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!
输入描述
The first (and only) line has three integers T, A, and B.
输出描述
A single integer, representing the maximum fullness Bessie can achieve.
示例1
输入:
8 5 6
输出:
8
C++(clang++11) 解法, 执行用时: 5ms, 内存消耗: 3940K, 提交时间: 2020-12-19 15:24:45
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int t,b,c,ans;
bool used[5000001][2];
void dfs(int res,bool hav)
{
if(res > t) return;
if(used[res][hav]) return;
used[res][hav] = 1;
ans = max(ans,res);
dfs(res + b,hav);
dfs(res + c,hav);
if(!hav)
dfs(res / 2,1);
}
int main()
{
cin>>t>>b>>c;
dfs(0,0);
cout<<ans;
}