【区间dp】Treats for the Cows POJ - 3186

梦里梦外; 2022-06-10 03:51 253阅读 0赞

Think:
1知识点：区间dp
2题意：给定一个长度为n的序列，从1开始取n次，每次可以选取第一个结点或者最后一个结点，每次获取的价值为当前次数乘以选取的结点数值，询问经过n次选取后所获得的总价值最大值
3思路：逆向思考，从最后一个获取的结点开始从里向外更新，逐渐恢复原始序列

vjudge题目链接

以下为Accepted代码

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  5. using namespace std;
  7. const int N = 2014;
  9. int a[N], dp[N][N];
  11. int main(){
  12.     int n, i, j, k;
  13.     while(~scanf("%d", &n)){
  14.         for(i = 1; i <= n; i++){
  15.             scanf("%d", &a[i]);
  16.             dp[i][i] = a[i]*n;/*初始化假设以当前结点作为最后获取结点进而从里往外试探最优解*/
  17.         }
  18.         for(k = 1; k < n; k++){
  19.    /*枚举区间长度*/
  20.             for(i = 1; i+k <= n; i++){
  21.                 j = i+k;/*区间右端点*/
  22.                 dp[i][j] = max(dp[i+1][j]+a[i]*(n-k), dp[i][j-1]+a[j]*(n-k));/*思想：从里往外试探最优解*/
  23.             }
  24.         }
  25.         printf("%d\n", dp[1][n]);
  26.     }
  27.     return 0;
  28. }

发表评论

表情：
评论列表 （有 0 条评论，253人围观）

还没有评论，来说两句吧...

相关阅读

    相关 POJ 3186

    题意略。 思路：有一点区间dp的意思。 我令dp\[ i \]\[ j \]表示：区间\[1 , i\]和区间\[j , N\]按某种顺序插值排好，所能获得的最大值。 状

    系统管理员系统管理员/ 0 赞/ 133 阅读