【第72题】区间DP八连刷之（2）：[USACO06FEB] Treats for the Cows G/S

小码匠

发布于 2023-08-31 15:23:58

2270

发布于 2023-08-31 15:23:58

文章被收录于专栏：小码匠和老码农

【第72题】区间DP八连刷之（2）：[USACO06FEB] Treats for the Cows G/S

题目

题目原文请移步下面的链接

https://www.luogu.com.cn/problem/P2858
- 参考题解：https://www.luogu.com.cn/problem/solution/P2858
标签：OI、动态规划、区间DP

正解

感觉转移方程和这位神犇@Youngsc很像，具体的释义大家可以看看这位dalao的，~~我是不会告诉你这个正解是我一通瞎搞搞出来的……~~

dp_{i,j}

表达的是卖掉区间i～j所得到的价值，大概就转移方程的具体意义解释一下

因为后面所要选取的是要乘上天数的，所以每往后一天就要加上这一段区间的价值，这是前缀和的由来
那么又因为它只能从两边选取，所以肯定是从

dp_{i, j-1}

和

dp_{i + 1,j}

转移过来的，这个很好想到，老套路了

那么先从转移过来的值中选一个更大的，然后再按第一条所述加上往后一天得到的价值，就得到了完整的状态转移方程

最后注意下区间长度是由短变长的，i和j是一个加一个减

AC代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>

using namespace std;
#define endl '\n';

void best_coder() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<vector<int>> dp(n + 2, vector<int>(n + 1));
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        a[i] += a[i - 1];
    }
    for (int i = n; i >= 1; --i) {
        for (int j = i; j <= n; ++j) {
            dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]) + a[j] - a[i - 1];
        }
    }
    cout << dp[1][n];
}

void happy_coder() {
}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    // 返回
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2023-07-30，如有侵权请联系 cloudcommunity@tencent.com 删除