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

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條評論
主站蜘蛛池模板: 好吊妞在线成人免费 | 天天久久狠狠伊人第一麻豆 | 国产精品videossex激情 | 大片毛片女女女女女女女 | 久久国产精品二国产精品 | 毛片色毛片18毛片美女 | 亚洲欧美日韩一级特黄在线 | 国产成人综合自拍 | 久久精品资源站 | 国产亚洲一区二区三区在线观看 | 大色综合色综合资源站 | 一级毛片视频 | 国产精品久久久久桃色tv | 四虎国产精品永免费 | 亚洲伊人久久综合 | 国产一级毛片国产 | 全黄冷激性性视频 | 久久成人国产 | 久久精品无码一区二区三区 | 4虎在线| 久草香蕉在线视频 | 天天干天天干天天干天天干天天干 | 狠狠操狠狠操狠狠操 | 中国女人内谢69xxxxx高清 | 国产美女精品在线 | 香蕉久久网 | 亚洲aa在线 | 黄片毛片在线看 | 男人看的网址 | julia中文字幕在线 | 国产福利在线看 | 久久99影院网久久久久久 | 夜夜躁日日躁狠狠久久 | 香蕉视频毛片 | 亚洲一级毛片免费在线观看 | 青草视频.com | 91色综合| 精品视频在线免费观看 | 国产成人精品日本亚洲直接 | 日韩国产中文字幕 | 四虎影院永久地址 |