#include<iostream>    // 01背包 dp(i,j)=max( dp(i-1,j-1),dp(i-1,j+1)+d[i]) 
#include<string>
using namespace std;  // i 分钟数 j  剩余的体力 
int d[10010];
int dp[10010][510];
inline int max(int a1,int b1)
{
	if(a1>b1)
		return a1;
	else
		return b1;
}
int main()
{
	int n,m,i,j;
	while(scanf("%d %d",&n,&m)!=EOF)
	{
	for(i=1;i<=n;i++)
		scanf("%d",&d[i]);
	for(i=1;i<=n;i++)
	{
		for(j=0;j<=m+1;j++)
			dp[i][j]=-200000000;
	}
	dp[1][0]=0;
	dp[1][1]=d[1];
    for(i=2;i<=n;i++)
	{
		for(j=0;j<=m;j++)
		{
		if(j==0)
		   dp[i][0]=max( dp[i-1][1] , dp[i-1][0] );
		else
		  dp[i][j]=max( dp[i-1][j+1] , dp[i-1][j-1]+d[i] );
		}
	}
	printf("%d\n",dp[n][0]);
	}
	return 0;
}

• 简单的01背包，测了很多组数据都WA了，哪位大牛能帮忙看一下吗？？ (133) lwaybing 2010-09-20 16:46:49