吃一个第一种汉堡耗时m,吃一个第二种耗时n,给你 t 的时间，在尽量使得时间剩下少的情况下，问最多可以吃多少个汉堡，注意实在尽量是的时间剩下的比较少，意思就是 在能做到刚好把时间花完 是最优情况，以尽量多花时间为先决条件，用背包解决，在尽量耗完时间的情况下 再求 吃的最多，瞬秒
#include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long #define eps 1e-7 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector > G; //typedef pair P; //vector > ::iterator iter; // //map mp; //map ::iterator p; //#define IN freopen("c:\\Users\\linzuojun\\desktop\\input.txt", "r", stdin) //#define OUT freopen("c:\\Users\\linzuojun\\desktop\\output.txt", "w", stdout) int dp[10000 + 5]; int Time[10000 + 5]; void clear() { memset(dp,0,sizeof(dp)); memset(Time,0,sizeof(Time)); } int main() { int m,n,t; while(cin>>m>>n>>t) { clear(); int a[3] = {0,m,n}; for(int i=1;i<=2;i++) { for(int j=a[i];j<=t;j++) { if(Time[j] < Time[j - a[i]] + a[i]) { Time[j] = Time[j - a[i]] + a[i]; dp[j] = dp[j - a[i]] + 1; } if(Time[j] == Time[j - a[i]] + a[i]) dp[j] = max(dp[j],dp[j - a[i]] + 1); } } if(Time[t] == t) cout<