Treats for the Cows
Time Limit:1000MSMemory Limit:65536K
Total Submissions:4286Accepted:2173
Description
FJ has purchased N (1 <= N <= 2000) yummy treats for the cows who get money for giving vast amounts of milk. FJ sells one treat per day and wants to maximize the money he receives over a given period time.The treats are interesting for many reasons:Given the values v(i) of each of the treats lined up in order of the index i in their box, what is the greatest value FJ can receive for them if he orders their sale optimally?The first treat is sold on day 1 and has age a=1. Each subsequent day increases the age by 1.
Input
Line 1: A single integer, NLines 2..N+1: Line i+1 contains the value of treat v(i)
Output
Line 1: The maximum revenue FJ can achieve by selling the treats
Sample Input
513152
Sample Output
43
Hint
Explanation of the sample:Five treats. On the first day FJ can sell either treat #1 (value 1) or treat #5 (value 2).FJ sells the treats (values 1, 3, 1, 5, 2) in the following order of indices: 1, 5, 2, 3, 4, making 1×1 + 2×2 + 3×3 + 4×1 + 5×5 = 43.
Source
题意：
给你n个数的序列，取n次数，每次只能从序列的头或尾取，第i次获得的值为i*a[j],求取完或最大值。
题解：
区间dp,dp[i][j]表示i-j最优解，，dp[i][j]=max(dp[i+1][j]+a[i]*(n-l+1),dp[i][j-1]+a[j]*(n-l+1));
CODE：
#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<string>#include<algorithm>#include<cstdlib>#include<set>#include<queue>#include<stack>#include<vector>#include<map>#define N 2010#define Mod 10000007#define lson l,mid,idx<<1#define rson mid+1,r,idx<<1|1#define lc idx<<1#define rc idx<<1|1const double EPS = 1e-11;const double PI = acos ( -1.0 );const double E = 2.718281828;typedef long long ll;const int INF = 1000010;using namespace std;int n;int a[N];int dp[N][N];int main() {while(cin>>n) {for(int i=1; i<=n; i++)scanf("%d",&a[i]);memset(dp,0,sizeof dp);for(int l=1; l<=n; l++) {for(int i=1,j=l+i-1; j<=n; j++,i++) {dp[i][j]=max(dp[i+1][j]+a[i]*(n-l+1),dp[i][j-1]+a[j]*(n-l+1));}}printf("%d\n",dp[1][n]);}return 0;}
不然你大概会一直好奇和不甘吧——家门前的那条小路，
