本文共 1439 字，大约阅读时间需要 4 分钟。

题意：有n个treats放在一个长长的箱子里，只有箱子两端有开口，第i个treat的价值为v[i]，每个treat可获利v[i]*a，其中a为treat的“年龄”，显然“年龄”越大越值钱。每天只能卖出一个treat，设第一天a=1，随天数递增1，求能获得的最大价值。

分析：这道题一开始以为好像很简单，觉得只要用一维的dp就够了，当时的状态是这样子的：

dp[i]：表示前i天所能获得的最大价值； 后来百思不得其解，想不出dp[i]的转移方程，就改成： dp[i]：表示在第i天卖出某treat最划算。 方程为：dp[i]=min（v[front],v[end]），用sum求和。 似乎对了有几个样例，觉得没毛病，但提交了几遍都WA。 方程中使用了min函数有事先证明过，先卖v[i]小的，再卖v[i]大的更划算，但其实现在一想，这种做法应该不属于DP，而是属于贪心，显然，贪心在这里并不能在所有情况都得出最优解，事实上，这个dp也写得有点假呀，dp[i]跟前后的元素一点联系也没有。。。（所以以后如果再有这种情况，就该怀疑自己是不是错了，我想，dp应该是一个与前或后都有紧密联系的算法，而非独立的）

于是，在网上看了大佬的博客，方发现，这道题应当用二维数组来做，属于区间dp

博客链接：

思路：

dp[i,j]：表示从第i个到第j个treat能够获得的最大价值；

dp[i,j]=max（dp[i+1,j]+v[i]×(n+i-j)，dp[i,j-1]+v[j]×(n+i-j)）； 解释一下为什么是n+i-j，这是表示“年龄”，举两个特例就可以确定了，比如i=1,j=n，那么“年龄”a=n+1-n=1，再如i=2,j=n-1,a=n+2-(n-1)=3。 最终答案：dp[1,n]（想想，这样的话那么循坏的方向应该怎么决定呢） 边界：

当i>j时，是没有什么意义的，因此设置循坏时可以跳过这些；

当i=j=k时，即dp[k,k]，这个时候表示只剩下一个treat了，而且已经到了最后一天了，因此应将dp[k,k]=v[k]×n。

代码如下：

#include
   
    #include
    
     using namespace std;long long v[2005],dp[2005][2005];int main(){	int n,i,j;	scanf("%d",&n);	for(i=1;i<=n;i++)	    scanf("%d",&v[i]);	for(i=n;i>=1;i--)	{		for(j=i;j<=n;j++)		{			if(i==j)			    dp[i][j]=v[i]*n;			else			    dp[i][j]=max(dp[i+1][j]+v[i]*(n+i-j),dp[i][j-1]+v[j]*(n+i-j));		}	}	printf("%lld\n",dp[1][n]);	return 0;}
    
   

小结：

1.这道题较有收获的是，让我这个小白知道，dp[i,j]的i,j是可以表示同一个意义的，而就目前个人的水平来理解，区间dp这一类题，应该都有这个特点，就是它的i,j意义是相同的； 2.后来自己有在推，不太清楚这个“年龄”怎么表示，以后如有这种情况，不要死脑筋，举两个特例就ok啦； 3.边界很重要，做DP题时要考虑好，这道题就是，此外，还要注重循环的方向，可以从最终答案的形式去确定。

转载地址：http://pfdci.baihongyu.com/