笨蛋就業(yè)了，并且是在上千應(yīng)聘中脫穎而出的，和他一起脫穎而出的還有傻子。公司的老板對(duì)二人視為珍寶，為了激勵(lì)他們的工作熱情，給他們一小時(shí)發(fā)一次工資（很高興吧）。但每次只發(fā)給一個(gè)人，并且每次發(fā)的工資可能不同（老板很厲害吧）。傻子和笨蛋為了證明自己比對(duì)方智商高，他們事先知道每次發(fā)的工資的多少。他們暗中達(dá)成協(xié)議：他們不是將工資平分，而是輪流領(lǐng)取。該領(lǐng)工資的人可以選擇跳過一個(gè)或多個(gè)小時(shí)的工資，而領(lǐng)取后面的工資。跳過的工資會(huì)捐給孤兒院。他們只管自己獲得最大利益，不管對(duì)方獲得的利益如何，每次笨蛋先領(lǐng)。比如 100， 100， 800， 70， 150 ,100。笨蛋第一個(gè)小時(shí)不領(lǐng)，第二個(gè)小時(shí)也不領(lǐng)，直接領(lǐng)第三個(gè)小時(shí)發(fā)的工資，傻子領(lǐng)第四個(gè)小時(shí)發(fā)的工資，笨蛋再領(lǐng)第五個(gè)小時(shí)發(fā)的工資，傻子再領(lǐng)第六個(gè)小時(shí)發(fā)的工資，這樣笨蛋領(lǐng)到950元的工資，傻子領(lǐng)到170元的錢，其余的全部捐給孤兒院為200元。

Input

多組測(cè)試數(shù)據(jù)
第一行輸入t，表示共發(fā)t個(gè)小時(shí)的工資（0<t<120）
接下來一行是t個(gè)數(shù)表示t小時(shí)內(nèi)每個(gè)小時(shí)的工資Money(0<money<10000)

Output

三個(gè)數(shù)字M,N，V
他們分別表示笨蛋領(lǐng)的工資，傻子領(lǐng)的工資，還有捐給孤兒院的錢

Sample Input

6 100 100 800 70 150 100 3 100 100 100

Sample Output

950 170 200 200 100 0 利用dp和貪心的思想；

AC代碼：

#include<iostream> #include<cstdio> #include<cmath> using namespace std; int main() {int t,sum;int M,N,V;int i,j;int dp[130];while(cin>>t){sum=0;for(i=0;i<t;i++){cin>>dp[i];sum+=dp[i];}M=N=0;for(i=t-1;i>-1;i--){if(dp[i]+M>=N){ //輪換選取最大值，滿足條件更新 V=N;N=dp[i]+M;M=V;}}cout<<N<<" "<<M<<" "<<sum-M-N<<endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的笨蛋的难题（二）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。