比較巧妙的動態(tài)規(guī)劃。用f[i][j]表示第i個月，總工作了j道題目（從1~j），所能剩余的最多錢數(shù)。

狀態(tài)轉(zhuǎn)移方程如下：

f[i][j]=Max(m-∑b[j]-∑b[k]){其中，k應(yīng)當(dāng)滿足f[i-1][k]>=∑a[j]-∑a[k]}

注意最后輸出的應(yīng)該是ans+1，因為第一個月實際上是沒有收入的。

代碼：

Program Psolve;//By_Thispoet Constmaxn=300; Vari,j,k,m,n,p,q,ans :Longint;a,b :Array[0..maxn]of Longint;f :Array[0..maxn*2,0..maxn]of Longint;Function Max(i,j:Longint):Longint; beginif i>j then exit(i);exit(j); end;BEGINreadln(m,n);for i:=1 to n dobeginreadln(a[i],b[i]);inc(a[i],a[i-1]);inc(b[i],b[i-1]);end;fillchar(f,sizeof(f),128);f[1,0]:=m;ans:=1;while true dobegininc(ans);for j:=1 to n dofor k:=j downto 0 dobeginif (f[ans-1][k]>=a[j]-a[k])and(m>=b[j]-b[k]) thenf[ans,j]:=Max(f[ans,j],m-b[j]+b[k]);if f[ans,j]=m then break;end;if f[ans,n]>=0 then break;end;writeln(ans+1);END.

轉(zhuǎn)載于:https://www.cnblogs.com/Thispoet/archive/2011/09/20/2182020.html

總結(jié)

以上是生活随笔為你收集整理的POJ3265 Problem Solving ——动态规划——Pku3265的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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