亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

POJ 1976 A Mini Locomotive

系統(tǒng) 1621 0

題意:有三個火車頭,每個最多能拉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!


POJ 1976 A Mini Locomotive


更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯(lián)系: 360901061

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

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發(fā)表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 精品国产免费久久久久久 | 久久国产乱子伦精品免 | 在线免费毛片 | 这里只有久久精品 | 欧美性精品不卡在线观看 | 国产在线观看成人免费视频 | 性欧美久久 | 午夜精品久久久久久久爽 | 我要看免费的毛片 | 欧美一级久久久久久久久大 | 久久精品综合免费观看 | 888米奇色狠狠俺去啦 | 美女视频黄是免费的 | 亚洲精品中文字幕区 | 国产国拍亚洲精品永久不卡 | 99精品视频只99有精品 | 日韩中文字幕视频在线观看 | 日韩欧美福利 | 久久这里只有精品9 | 色在线视频 | 国产高清在线精品一区二区三区 | 老司机免费精品视频 | 热久久这里只有 | 成人国产精品毛片 | 第一区免费在线观看 | 日韩欧美三区 | 四虎永久免费紧急入口 | 色妇色综合久久夜夜 | 国产高清美女一级a毛片久久 | 亚洲精品一区最新 | 久久精品站 | 亚洲午夜久久久久中文字幕久 | 真人女人一级毛片免费视频观看 | 成人精品一级毛片 | 免费色片 | 四虎爱爱| 大陆国产精品视频 | 青青青草视频在线观看 | 国产福利福利视频 | 久草久草 | 久草6|