一天，歐姆諾諾姆來到了朋友家里，他發(fā)現(xiàn)了許多糖果。有藍(lán)色和紅色兩種。他知道每顆紅色糖果重Wr克，每顆藍(lán)色糖果重Wb克。吃一顆藍(lán)色糖果會給他帶來Hb的歡樂值，吃一顆紅色糖果會給他帶來Hr的歡樂值。

歐姆諾姆最多只能吃C克的糖果，而且每一顆糖果不能只吃一半。現(xiàn)在他想通過吃藍(lán)色和紅色的糖果來獲得最大的歡樂值。

樣例解釋：每一種糖果吃兩顆即可。

單組測試數(shù)據(jù)。輸入占一行有四個(gè)整數(shù)C,Hr,Hb,Wr,Wb (1≤C,Hr,Hb,Wr,Wb≤10^9).Output
輸出最大可能獲得的歡樂值。Input示例
樣例輸入110 3 5 2 3Output示例
樣例輸出116
思路：
1、我們將問題分成九種情況討論：
①wr>wb&&hr>hb
②wr>wb&&hr=hb
③wr>wb&&hr<hb
④wr=wb&&hr>hb
⑤wr=wb&&hr=hb
⑥wr=wb&&hr<hb
⑦wr<wb&&hr>hb
⑧wr<wb&&hr=hb
⑨wr<wb&&hr<hb
不難討論出，第二種，第三種，第六種情況，全部吃藍(lán)色糖豆是最劃算的。
同理，第四種，第七種，第八種情況，全部吃紅色糖豆是最劃算的。
對于第五種情況，相當(dāng)于只有一種糖豆，那么也可以看做全部吃藍(lán)色糖豆是最劃算的。
那么對于第一種和最后一種情況。
我們肯定是貪心將肚子填滿，盡量不要有空余的空間沒有使用，假設(shè)我們此時(shí)吃紅色糖豆最多（i個(gè)），那么剩余的空間，我們是要吃藍(lán)色糖豆的（j個(gè)），對于這種情況，最好使得i*wr+j*wb==c.而且我們希望滿足這種情況的同時(shí)，將開心值最大化。那么肯定我們是要吃某種糖豆更多一些（那種糖豆的單位開心值更大一些），然后希望湊出來一種情況，使得這種吃糖豆最多的同時(shí)，不浪費(fèi)肚子的空間（當(dāng)然也有可能浪費(fèi)空間也是最優(yōu)方案的情況）。
情況種類很多。這時(shí)我們討論不出一定所以然的公式出來，那么我們不妨枚舉少一點(diǎn)的糖豆會吃多少個(gè)，那么剩余的肚子的空間就留給另一種糖豆了，1s的時(shí)限，我們可以枚舉到1e7也無妨。
Ac代碼：
#include<stdio.h>#include<iostream>#include<string.h>using namespace std;#define ll __int64ll c,hr,hb,wr,wb;void allblue(){    ll output=(c/wb)*hb;    ll yu=c%wb;    output+=(yu/wr)*hr;    PRintf("%I64d/n",output);}void allred(){    ll output=(c/wr)*hr;    ll yu=c%wr;    output+=(yu/wb)*hb;    printf("%I64d/n",output);}int main(){    while(~scanf("%I64d%I64d%I64d%I64d%I64d",&c,&hr,&hb,&wr,&wb))    {        if(wr>wb&&hr==hb||wr>wb&&hr<hb&&wr==wb&&hr<hb)        {            allblue();        }        else if(wr==wb&&hr>hb&&wr<wb&&hr>hb&&wr<wb&&hr==hb)        {            allred();        }        else if(wr==wb&&hr==hb)        {            allblue();        }        else        {            ll output=0;            for(int i=0;i<=10000800;i++)            {                if(i*wr<=c)                {                    ll tmp1=i*hr;                    ll yu=c-(i*wr);                    tmp1+=(yu/wb)*hb;                    output=max(output,tmp1);                }                if(i*wb<=c)                {                    ll tmp1=i*hb;                    ll yu=c-(i*wb);                    tmp1+=(yu/wr)*hr;                    output=max(output,tmp1);                }            }            printf("%I64d/n",output);        }    }}當(dāng)然代碼可以簡化：
#include<stdio.h>#include<iostream>#include<string.h>using namespace std;#define ll __int64ll c,hr,hb,wr,wb;int main(){    while(~scanf("%I64d%I64d%I64d%I64d%I64d",&c,&hr,&hb,&wr,&wb))    {        ll output=0;        for(int i=0; i<=10000800; i++)        {            if(i*wr<=c)            {                ll tmp1=i*hr;                ll yu=c-(i*wr);                tmp1+=(yu/wb)*hb;                output=max(output,tmp1);            }            if(i*wb<=c)            {                ll tmp1=i*hb;                ll yu=c-(i*wb);                tmp1+=(yu/wr)*hr;                output=max(output,tmp1);            }        }        printf("%I64d/n",output);    }}