kuangbin专题十二 POJ3186 Treats for the Cows （区间dp）-白红宇

kuangbin专题十二 POJ3186 Treats for the Cows （区间dp）

阅读量：7115 次

发布时间：2019-06-28

本文共 3165 字，大约阅读时间需要 10 分钟。

Treats for the Cows

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 7949		Accepted: 4217

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:

The treats are numbered 1..N and stored sequentially in single file in a long box that is open at both ends. On any day, FJ can retrieve one treat from either end of his stash of treats.

Like fine wines and delicious cheeses, the treats improve with age and command greater prices.

The treats are not uniform: some are better and have higher intrinsic value. Treat i has value v(i) (1 <= v(i) <= 1000).

Cows pay more for treats that have aged longer: a cow will pay v(i)*a for a treat of age a.

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, N

Lines 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

Sample Output

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 1x1 + 2x2 + 3x3 + 4x1 + 5x5 = 43.

题目大意：给一个长度为n的序列，每次只能从队首或队尾取一个数，第几次取 * f[i] 就是利润，求最大利润。

看到题目果断贪心，只能局部最优，因为是dp专题，但是丝毫不会dp，看了题解发现是区间dp，然后看着理解了一下，

dp[i][j] 表示从第i个数到第j个数的最大利润，由于只能从dp[i+1][j] 和 dp[i][j-1]到达dp[i][j]，所以状态转移方程可以表示为 dp[i][j] = max(dp[i+1][j] + f[i] * (n-j+i), dp[i][j-1] + f[j] * (n-j+i),

这里是由里向外递推的，逆向遍历i。用n-j+i表示第几次取（可以模拟一个简单的看看）

初始化条件要注意一下，dp[i][i] = f[i] * n 只有一个数时，它就是最后取的。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             10 #include 
              
               11 #include 
               
                12 #include 
                
                 13 #include 
                 
                  14 using namespace std;15 #define mem(a,b) memset((a),(b),sizeof(a))16 #define mp make_pair17 #define pb push_back18 #define fi first19 #define se second20 #define sz(x) (int)x.size()21 #define all(x) x.begin(),x.end()22 typedef long long ll;23 const int inf = 0x3f3f3f3f;24 const ll INF =0x3f3f3f3f3f3f3f3f;25 const double pi = acos(-1.0);26 const double eps = 1e-5;27 const ll mod = 1e9+7;28 //head29 const int maxn = 2000 + 5;30 int dp[maxn][maxn], f[maxn];//dp[i][j] 表示从i到j的 最大值31 32 int main() {33 int n;34 while(~scanf("%d", &n)) {35 for(int i = 1; i <= n; i++)36 scanf("%d", &f[i]);37 mem(dp, 0);38 for(int i = 1; i <= n; i++)//初始化 每一个都是最后取的39 dp[i][i] = f[i] * n;40 for(int i = n - 1; i >= 1; i--) { //从里往外推41 for(int j = i + 1; j <= n; j++) { // n - j + i 很巧妙42 dp[i][j] = max(dp[i+1][j] + f[i] * (n - j + i), dp[i][j-1] + f[j] * (n - j + i));//转移方程43 }44 }45 printf("%d\n", dp[1][n]);46 }47 }

转载于:https://www.cnblogs.com/ACMerszl/p/9572925.html

你可能感兴趣的文章

区块链和数据科学：如果同时应用这两种技术，将会实现什么?