題意:有三個火車頭,每個最多能拉k個車廂,一共有n個車廂,每個車廂里都有乘客,每個火車頭拉的車廂都是連續(xù)的。問能拉的最多的乘客數(shù)。
分析:先一看好像沒有什么思路,然后用動態(tài)規(guī)劃的思想慢慢想:
假設(shè)F[i][j]表示用i個火車頭在前j個車廂中能拉的最大乘客數(shù)。考慮第j個車廂被拉還是不被拉~可得狀態(tài)方程:
F[i][j] = max(F[i][j-1], F[i-1][j-k]+ b[j])
b[j]表示從j-k+1到j(luò)的k節(jié)車廂的總的人數(shù),可以把這k節(jié)車廂看成一個整體,如果拉這k節(jié)車廂,則F[i][j]就是用i-1個火車頭在前j-k個車廂中能拉的最大乘客數(shù)加上這k節(jié)車廂的人數(shù),若不拉,則F[i][j]就是用i個火車頭在前j-1個車廂中能拉的最大乘客數(shù) 注意,一定是F[i][j-1]而不是F[i][j-k]。而且一定是k個車廂整體考慮!
好了,有了狀態(tài)方程,那這就是一個DP問題,是不是so easy?
上代碼:
?
#include <iostream> using namespace std; int nCoachs; int k; int F[4][50001]; int a[50001];//存放每節(jié)車廂的人數(shù) int b[50001]; int max(int a, int b) { return a>b?a:b; } int main(int argc, char **argv) { int nTests, sum; cin>>nTests; while (nTests--) { cin>>nCoachs; for (int i=1; i<=nCoachs; ++i) cin>>a[i]; cin>>k; a[0] = 0; sum = 0; b[0] = 0; //求出b[j],j>=k for(int i=1;i<=k;i++) { b[i]=b[i-1]+a[i]; } sum=b[k]; for(int i=k+1;i<=nCoachs;i++) { sum+=a[i]; sum-=a[i-k]; b[i]=sum; } for (int i=1; i<=3; ++i) { for (int j=k; j<=nCoachs; ++j) { F[i][j]=max(F[i-1][j-k]+b[j],F[i][j-1]); } } cout<<F[3][nCoachs]<<endl; } system("pause"); return 0; }
?
?
32MS過!done!
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯(lián)系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
