软件实践工程OJ-1151 款带奶牛(treat) 区间dp算法分析：代码实现：

62 阅读 0 评论 41 点赞

我是靠谱客的博主健壮航空，最近开发中收集的这篇文章主要介绍软件实践工程OJ-1151 款带奶牛(treat) 区间dp算法分析：代码实现：，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述：

FJ有n（1≤n≤2000）个美味的食物，他想卖掉它们来赚钱给奶牛。这些食物放在一些箱子里，它们有些有趣的特性：
（1）这些食物被编号为1～n，每一天FJ可以从这排箱子的头部或者尾部取出食物去卖；
（2）这些食物放得越久，年龄越大，价值越大，食物i有一个初始的价值V(i)；
（3）放了a天后，年龄为a，食物最终的价值为V(i)×a。

给定每一个食物的初始价值v(i)，请求出FJ卖掉它们后可以获得的最大价值，第一天出售的食物的年龄为1，此后每增加一天食物的年龄就增加1。

输入：

第1行：一个整数n；
第i+l行：每行为食物i的初始价值V(i)。

输出：

1行：FJ最终可以获得的最大价值。

样例输入：

5
1
3
1
5
2

样例输出：

算法分析：

这道题用到了传说中的区间dp，我对dp不是很熟练（太水了）。废了老大劲才搞明白。

代码实现：

#include <stdio.h>
#include <string.h>

#include <iostream>
#include <algorithm>

using namespace std;

int n;
int a[2200];
int dp[2200][2200];

int main()
{
    while (scanf("%d", &n) != EOF) {
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n-i+1; j++) {
                dp[j][i] = max(dp[j+1][i-1] + (n-i+1)*a[j], dp[j][i-1] + (n-i+1)*a[j+i-1]);
            }
        }
        printf("%dn", dp[1][n]);
    }

    return 0;
}