Codeforces 148E Porcelain 预处理+双向dp+背包

传送门：https://codeforces.com/contest/148/problem/E

题意

有n层货架，每层货架都有a_i本书，每本书都有自己的价值。 拿书只能在一层的左右拿书，问拿m本书的最大价值。

思路

这题难在每层拿书只能左右拿，如果不需要左右拿，那么就是个背包问题。

如果处理这个左右拿呢？

因为每层都可能拿书，所以需要处理每层拿j本书的最大价值，而且是左右拿。

设sum[i][j]表示独立的第i层拿了j本书的最大价值。 这j本可以是前j本，也可以后j本，也可以两边都有。

假设前面拿了k本，那么后面就拿了j-k本。 前k本价值，所以需要处理每层的前缀和。 转移方程为： $$sum[i][j]=max(sum[i][j],pre[i][k]+pre[i][v]-pre[i][v-j-k])(v表示该层书总数)$$

然后就知道每一层该拿多少本书的最大价值了。

之后就是一层一层递推了（背包）.

先处理边界，也就是拿第一层书。然后推第二层、三、..

设dp[i][j]表示前i层拿了j本的最大价值。

则：$dp[1][i] = sum[1][i]$

枚举每一层，再枚举一共拿了j本书，最后枚举拿了当前层的k本书。 状态转移方程为：

$$dp[i][j]=max(dp[i][j],dp[i-1][j-k]+sum[i][k])$$ $ans=max(dp[i][j],ans)$处理答案即可。

复杂度为$O(n*n*m)$，由于常数较小，所以可以过。

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
##include "bits/stdc++.h"

using namespace std;

const int N = 205;
int sum[N][N]; // 独立第i层拿了j本书第最大价值
int dp[N][20005]; // 到了第i层拿了j本书的最大价值

void solve() {
    int n, m; cin >> n >> m;
    vector<int> a[n + 1], pre[n + 1];
    for(int i = 1;i <= n; i++) {
        int k; cin >> k;
        a[i].eb(0);
        pre[i].eb(0);
        for(int j = 1;j <= k; j++) {
            int x; cin >> x;
            pre[i].eb(pre[i][j - 1] + x);
            a[i].eb(x);
        }
    }
    for(int i = 1;i <= n; i++) { // 第i层
        int last = pre[i].size() - 1;
        for(int j = 0;j <= last; j++) { // 拿了j本书
            for(int k = 0;k <= j; k++) { // 前k本，后j-k本
                if(k == 0) sum[i][j] = max(sum[i][j], pre[i][last] - pre[i][last - j]);
                else sum[i][j] = max(sum[i][j], pre[i][k] + pre[i][last] - pre[i][last - j + k]);
            }
        }
    }
    int ans = 0;
    for(int i = 0;i <= m; i++) {
        dp[1][i] = sum[1][i];
        ans = max(ans, dp[1][i]);
    }
    for(int i = 1;i <= n; i++) {
        for(int j = 0;j <= m; j++) {
            for(int k = 0;k < pre[i].size() && k <= j; k++) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k] + sum[i][k]);
                ans = max(dp[i][j], ans);
            }
        }
    }
    cout << ans << endl;
}

signed main() {
    solve();
}

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