USACO 2015 December Contest, Gold Problem 2. Fruit Feast

每個方法可以表現成x*A+y*B + (z*A + u*B)/2

那麼，就可以輕鬆過了XDDD

#include <iostream>

#include <stdio.h>

#include <algorithm>

#include <cstring>

using namespace std;

const int MAX_T = 5000002;

int dp[MAX_T];

int main () {

freopen("feast.in","r",stdin);

freopen("feast.out","w",stdout);

int T,a,b;

while (scanf("%d %d %d",&T,&a,&b) != EOF) {

memset(dp,0,sizeof(dp));

for (int x=a;T>=x;x+=a) dp[x]=x;

for (int x=b;T>=x;x+=b) dp[x]=x; 

for (int x=1;T>=x;x++) {

if (dp[x]==x && x+b<=T) dp[x+b]=x+b;

}

// puts("hi");

int ans=-1;

for (int x=1;T>=x;x++) {

// cout << "dp["<<x<<"]="<<dp[x]<<endl;

if (dp[x]==x) {

int t1=dp[x];

if (ans<t1) ans=t1;

int t2=dp[x] + (a/2);

if (ans<t2 && t2<=T) ans=t2;

t1=dp[x] + (b/2);

if (ans<t1 && t1<=T) ans=t1;

t2=dp[x] + (a+b)/2;

if (ans<t2 && t2<=T && a+b<=T) ans=t2;

}

// cout<<ans<<endl;

} 

printf("%d\n",ans);

}

}