bzoj4393【Usaco2015 Dec】Fruit Feast

bzoj4393【Usaco2015 Dec】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!

奶牛Bessie潛入了農夫約翰的家，她發現這裡有無窮無盡的檸檬派和橘子派。

Bessie的飽脹值一開始是0，且上限是T，每個檸檬派可以提供A點飽脹值，每個橘子派可以提供B點飽脹值。

Bessie可以不斷地吃東西，如果她的飽脹值沒有超出T的話。同時，Bessie有一次喝水的機會，喝完後，她的飽脹值將減少一半（往下取整）。

請計算出Bessie的飽脹值最多可以達到多少。

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

Sample Output

HINT

Source

#include
#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define pa pair
#define maxn 5000100
#define inf 1000000000
using namespace std;
int a,b,t,ans;
bool f[maxn][2];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int main()
{
	t=read();a=read();b=read();
	f[0][0]=true;
	F(j,0,1) F(i,0,t) if (f[i][j])
	{
		if (i+a<=t) f[i+a][j]=true;
		if (i+b<=t) f[i+b][j]=true;
		if (!j) f[i/2][1]=true;
	}
	ans=t;
	while (!f[ans][0]&&!f[ans][1]) ans--;
	printf("%d\n",ans);
}