poj 3186區間dp

poj 3186區間dp

給你一個數列 然後從裡面取數 只能從隊頭或隊尾取出 取出的值乘以取出的順序i（及第幾個取出的） 求累加和的最大值；

dp【i】【j】表示去了i次 從左邊去了j個的最大值； 然後地推下去；

dp【i】【j】=max（dp【i-1】【j】*num【j】*i，num【i-1】【j】+num【n-i+j+1】*i）注意j為0的情況；再說這道題坑吧 num數組開為局部變量wa 開為int64 還是wa 真是無語了

#include
#include
#include
using namespace std;

int dp[2010][2010],num[2010];
int max(int a,int b)
{
	return a>b?a:b;
}
int main()
{
	int n,i,j;
	while(~scanf("%d",&n))
	{
		for(i=1;i<=n;i++)
		scanf("%d",&num[i]);
		memset(dp,0,sizeof(dp));
		for(i=1;i<=n;i++)
		{
			for(j=0;j<=i;j++)
			{
				if(j>0)dp[i][j]=max(dp[i-1][j-1]+num[j]*i,dp[i-1][j]+num[n-i+j+1]*i);
				else dp[i][j]=dp[i-1][j]+num[n-i+j+1]*i;
			}
		}
		int Max=0;
		for(i=0;i<=n;i++)
		{
			Max=max(Max,dp[n][i]);
			//printf("%I64d\n",dp[n][i]);
		}
		printf("%d\n",Max);
	}
	return 0;
}