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

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條評論
主站蜘蛛池模板: 久久国内精品自在自线观看 | 素人视频在线观看 | 久久视频精品a线视频在线观看 | 91精品国产欧美一区二区 | 精品综合久久久久97 | 香蕉免费一级视频在线观看 | 国产成人久久精品一区二区三区 | 日本一区二区三区高清在线观看 | 香蕉观看在线视频成人 | 欧美成人免费观看久久 | 九九re6精品视频在线观看 | 久久综合综合久久狠狠狠97色 | 欧美日韩中文视频 | 久久国产综合精品欧美 | 一区二区三区在线 | 欧 | 狠狠色狠狠色综合久久第一次 | 玖玖射| 亚州精品一区二区三区 | 人成午夜视频 | 久久精品国产亚洲婷婷 | 九九国产精品九九 | 九色视频网 | 国内精品福利在线视频 | 欧美成人午夜影院 | 久久国产欧美日韩高清专区 | 久久国产成人 | 狠狠色视频 | 国产一区二区三区在线影院 | 亚洲一区二区三区免费看 | 久久国产精品亚洲77777 | 久久夜色精品国产欧美 | 日本三级欧美三级 | 亚洲成人国产 | 精品免费视在线观看 | 亚洲成综合 | 欧美xxxx4khd超高清 | 欧美成人剧情中文字幕 | 精品国产免费人成高清 | 日韩我不卡 | 97在线视频免费公开观看 | 国产毛片视频 |