poj 3661 Running dp

poj 3661 Running dp

題意：

有n分鐘時間，每分鐘牛能跑d[i]路程，在每分鐘，牛可以選擇跑，這樣疲勞度會+1，也可以選擇不跑，這樣疲勞度會-1（最少到0），問n分鐘後疲勞度為0時最多能跑多遠，注意牛要疲勞度為0才能繼續跑。

分析：

設dp[i][j]表示i分鐘結束奶牛疲勞度為j時能跑的最遠距離，則轉移有：dp[i-1][j-1]->dp[i][j]+d[i]，dp[i][j]->dp[i+j][0];

代碼：

//poj 3661
//sep9
#include 
using namespace std;
const int maxN=10024;
int v[maxN];
int dp[maxN][512];
int main()
{
	int i,j,n,m;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i)
		scanf("%d",&v[i]);
	for(i=0;i<=n;++i)
		for(j=0;j<=m+1;++j)
			dp[i][j]=INT_MIN;
	dp[0][0]=0;
	for(i=1;i<=n;++i)
		for(j=0;j<=m;++j){
			if(j>0)
				dp[i][j]=max(dp[i][j],dp[i-1][j-1]+v[i]);
			if(i+j<=n)
				dp[i+j][0]=max(dp[i+j][0],dp[i][j]);
			if(j==0)
				dp[i][j]=max(dp[i][j],dp[i-1][j]);
		}
	printf("%d",dp[n][0]);
	return 0;	
}