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

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條評論
主站蜘蛛池模板: 色在线视频 | 伊人久久国产免费观看视频 | 国产成人精品在视频 | 欧美日韩麻豆 | 中文字幕欧美亚洲 | 站长推荐国产午夜免费视频 | 伊人色综合一区二区三区 | 日本免费黄色录像 | 久久亚洲网 | se94se在线看片secom | 亚洲一区视频 | 久热这里只有精品99国产6 | 国产一区二区久久 | 黄色在线观看免费 | 日日草夜夜草 | 亚洲视频1 | 天天干天天操天天舔 | 91国在线高清视频 | 国产深夜 | 欧美成人另类69 | 国产精品日韩欧美一区二区 | 成人精品视频在线观看 | 思99热精品久久只有精品 | 二区国产| 老司机午夜在线视频免费观 | 中文国产成人精品久久一区 | 国内精品伊人久久大香线焦 | 亚洲最大成人网 色香蕉 | 奇米影视一区二区三区 | 操久在线 | 国产羞羞事1000部在线观看 | 日韩中文字幕精品一区在线 | 一级a毛片免费观看久久精品 | 日本一级特黄毛片免费视频9 | 青青青免费在线视频 | 国产美女a做受大片在线观看 | 奇米影视第四色首页 | 簧片在线播放 | 久久久网久久久久合久久久久 | 成人精品在线 | 国产或人精品日本亚洲77美色 |