Codeforces 358D - Dima and Hares DP

传送门：http://codeforces.com/problemset/problem/358/D

题意

有n匹马排列在草场上，每只马如何吃草很有讲究。

  • 如果左右的两匹马都没吃，他吃了，价值增加a[i]
  • 如果左右的两匹马有一只吃了，他吃了，价值增加b[i]
  • 如果左右的两匹马都吃了，他吃了，价值增加c[i]

问怎么吃，才能使总价值最大。

思路

显然吃的顺序对答案有影响，也就是求出一个排列使得价值最大。

排列？3000？显然复杂度不够，我们发现每只马吃草，只有左右两匹马的作用会对该马有影响。

所以，讨论这匹马左右两边的状态。

设dp[i][0/1]为我们的状态。 dp[i][0]表示第i匹马比第i-1匹马后吃草. dp[i][1]表示第i匹马比第i-1匹马先吃草.

根据我们的状态进行转移：

1
2
dp[i][0] = max(dp[i - 1][0] + b[i - 1], dp[i - 1][1] + a[i - 1]);
dp[i][1] = max(dp[i - 1][0] + c[i - 1], dp[i - 1][1] + b[i - 1]);

注意边界的马，不是一匹“完整”的马。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
##include "bits/stdc++.h"
using namespace std;

const ll INF = 0x3f3f3f3f;

const int N = 3005;
int dp[N][2];

void solve() {
    int n; cin >> n;
    vector<int> a(n + 1), b(n + 1), c(n + 1);
    for(int i = 1;i <= n; i++) cin >> a[i];
    for(int i = 1;i <= n; i++) cin >> b[i];
    for(int i = 1;i <= n; i++) cin >> c[i];
    dp[1][0] = -INF;
    dp[1][1] = 0;
    for(int i = 2;i <= n + 1; i++) {
        dp[i][0] = max(dp[i - 1][0] + b[i - 1], dp[i - 1][1] + a[i - 1]);
        dp[i][1] = max(dp[i - 1][0] + c[i - 1], dp[i - 1][1] + b[i - 1]);
    }
    cout << dp[n + 1][0] << endl;
}

signed main() {
    solve();
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/04/09/codeforces-358d-dima-and-hares/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！