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