在该题中，请不要使用#include< bits/stdc++.h> 和任何c++11及以上的特性
给出n个数字v(i)，每次你可以取出最左边的数字或者取出最右边的数字，一共取n次取完。假设你第i次取的数字是x，那么你可以获得i*x的价值。现在你需要规划取数顺序，使得总价值和最大。

Input

第一行一个数字n(1<=n<=2000)。
下面n行每行一个数字v(i)。(1<=v(i)<=1000)

Output

输出一个数字，表示最大总价值和。

Sample Input

5
1
3
1
5
2

Sample Output

43

Hint

按照这种下标顺序取数： 1, 5, 2, 3, 4
1x1 + 2x2 + 3x3 + 4x1 + 5x5 = 43.

题目大意:中文题意我就不说啦

题目思路:起初对于这个题想到的是贪心,猜想之后发现不对,他无法保证后面过程是否为最优解.所以逆向思维考虑,从最后的状态一步步还原为初始状态,设dp[i][j] 表示 i-j内,我拿完能或得到的最大值,这样我们也可以发现 i==j的时候我们最终状态可以很好的确定就是  最后一个拿,所以初始化 对角线= num[i]*n,之后状态转移方程就可以得到了,i -> j 这个区间,是由 i->j-1 再加上j得到或者 i+1 ->j 再拿上i得到,所以状态转移方程:

dp[i][j]=max(dp[i][j-1]+(n-(j-i))*num[j]),dp[i+1][j]+(n-(j-i))*num[i])

所以两层for搞定:


//#include <bits/stdc++.h>
#include <stdio.h>
#include <algorithm>
#define E 2.718
using namespace std;
typedef long long ll;
const ll INF=0x7f7f7f7f;
const int maxn=1e6+8;
const double eps=1e-10;
const ll mod=1000000007;
ll n,m,b;
ll x,y;
ll num[2005];
ll dp[2005][2005];
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&num[i]);
    for(int i=1;i<=n;i++)
        for(int k=1;k<=n;k++) dp[i][k]=0;
    for(int i=1;i<=n;i++) dp[i][i]=n*num[i];
    for(int i=1;i<=n;i++)
    {
        for(int k=1;k+i<=n;k++)
        {
            int j=k+i;
            dp[k][j]=max(dp[k+1][j]+(n-i)*num[k],dp[k][j-1]+(n-i)*num[j]);
        }
    }
    printf("%lld\n",dp[1][n]);
    return 0;
}

总结:继续加油继续刷题题目见多了就不会觉得今天这个题是区间dp而惊讶了.