Treats for the Cows
先搬中文
Descriptions:
給你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
5
1
3
1
5
2
Sample Output
43
Hint
按照這種下標順序取數： 1, 5, 2, 3, 4
取出的數按順序為：1, 2, 3, 1, 5
最大總價值和：1x1 + 2x2 + 3x3 + 4x1 + 5x5 = 43.
題目鏈接：
https://vjudge.net/problem/POJ-3186
區間dp
dp[i][j] 代表從i取到j的最大總數
dp[i][j] = max(dp[i+1][j]+a[i]*(n+i-j) , dp[i][j-1]+a[j]*(n+i-j)) 即取右邊的數 取左邊的數 比較哪個大
AC代碼
#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #define Mod 1000000007 #define eps 1e-6 #define ll long long #define INF 0x3f3f3f3f #define MEM(x, y) memset(x, y, sizeof(x)) #define Maxn 2000+10 using namespace std; int n; int dp[Maxn][Maxn],a[Maxn]; int main() { MEM(dp,0); MEM(a,0); cin>>n; for(int i=0;i<n;i++) cin>>a[i]; for(int len=0;len<n;len++)//區間長度len { for(int i=0;i+len<n;i++)//固定區間左邊起點 { int l=i,r=i+len;//區間左、右點 //取右邊的數 取左邊的數 比較哪個大 dp[l][r]=max(dp[l+1][r]+a[l]*(n+l-r),dp[l][r-1]+a[r]*(n+l-r)); } } cout<<dp[0][n-1]<<endl; return 0; }
給你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
5 1 3 1 5 2
Sample Output
43
Hint按照這種下標順序取數： 1, 5, 2, 3, 4
取出的數按順序為：1, 2, 3, 1, 5
最大總價值和：1x1 + 2x2 + 3x3 + 4x1 + 5x5 = 43.
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/206286.html
標籤：其他