poj3186 Treats for the Cows(区间)

题目链接: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 ;
}
上一篇:原生js之canvas时钟组件


下一篇:Install a Jenkins on Ubuntu system