題目鏈接：http://poj.org/problem?id=3186

題意：第一個數(shù)是N，接下來N個數(shù)，每次只能從隊列的首或者尾取出元素。

ans=每次取出的值*出列的序號。求ans的最大值。

樣例 ：

input：5

　　　 ?1 2 1 5 2

output：43?

?

思路：區(qū)間dp，用兩個指針i和j代表區(qū)間，dp[i][j]表示這個區(qū)間的最大值。

///最開始想想著每次拿值最小的就好了，因為之前沒接觸過區(qū)間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[2005]; int dp[2005][2005];int main() {int n;while(cin>>n){for(int i=1; i<=n; i++)cin>>a[i];memset(dp,0,sizeof(dp));for(int i=1; i<=n; i++)dp[i][i]=a[i]*n;for(int l=1; l<n; l++){for(int i=1; i+l<=n; i++){int j=i+l;dp[i][j]=max((dp[i+1][j]+a[i]*(n-l)),(dp[i][j-1]+a[j]*(n-l)));}}cout<<dp[1][n]<<endl;}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/a-clown/p/5993349.html

總結(jié)

以上是生活随笔為你收集整理的poj3186 Treats for the Cows(区间)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。