题目链接：http://poj.org/problem?id=3186
题意：第一个数是N，接下来N个数，每次只能从队列的首或者尾取出元素。
ans=每次取出的值*出列的序号。求ans的最大值。
样例 ：
input：5
1 2 1 5 2
output：43
思路：区间dp，用两个指针i和j代表区间，dp[i][j]表示这个区间的最大值。
///最开始想想着每次拿值最小的就好了，因为之前没接触过区间dp，就这样naive的交了，意料之中的WA了。
///找到一个范例 eg：1000001 1000002 1000003 1000004 1000005 1 2 3 4 5 6 7 8 9 1000010 这个如果，诶次取最小的得到的就不是最大值
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std; int a[];
int dp[][]; int main()
{
int n;
while(cin>>n)
{
for(int i=; i<=n; i++)
cin>>a[i];
memset(dp,,sizeof(dp));
for(int i=; i<=n; i++)
dp[i][i]=a[i]*n;
for(int l=; l<n; l++)
{
for(int i=; i+l<=n; i++)
{
int j=i+l;
dp[i][j]=max((dp[i+][j]+a[i]*(n-l)),(dp[i][j-]+a[j]*(n-l)));
}
}
cout<<dp[][n]<<endl;
}
return ;
}