Treats for the Cows （简单dp）

给你n个数字v(1),v(2),...,v(n-1),v(n)，每次你可以取出最左端的数字或者取出最右端的数字，一共取n次取完。假设你第i次取的数字是x，你可以获得i*x的价值。你需要规划取数顺序，使获得的总价值之和最大。

Input

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

Output

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

Sample Input

Sample Output

Hint

按照这种下标顺序取数： 1, 5, 2, 3, 4
取出的数按顺序为：1, 2, 3, 1, 5
最大总价值

#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <iostream>
#include<vector>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <iostream>
using namespace std;
long long dp[2005][2005];
long long a[2005];
int main()
{
    //freopen("in.txt","w",stdout);
    memset(dp,0,sizeof(dp));
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i+1;j++)
        {
            dp[j][j+n-i-1]=max(dp[j-1][j-i+n-1]+i*a[j-1],dp[j][j-i+n]+i*a[j-i+n]);
           //44 cout<<j<<" "<<j+n-i-1<<" "<<dp[j][j+n-i-1]<<endl;
        }
    }
    long long ans=0;
    for(int i=1;i<=n;i++)
    {
        ans=max(dp[i][i-1],ans);
    }
    printf("%lld
",ans);
}

和：1x1 + 2x2 + 3x3 + 4x1 + 5x5 = 43.

dp的题目变形很广泛

其实dp最重要的部分就是 dp数组所记录的状态及状态转移方程

所以dp还是要多做题多熟悉各种变形