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

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

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

• • 题意
  • 思路
  • Code

题意

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

思路

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

如 果 处 理 这 个 左 右 拿 呢 ？ 如果处理这个左右拿呢？ 如果处理这个左右拿呢？

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

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

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

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

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

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

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

则 ： d p [ 1 ] [ i ] = s u m [ 1 ] [ i ] 则：dp[1][i] = sum[1][i] 则：dp[1][i]=sum[1][i]

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

d p [ i ] [ j ] = m a x ( d p [ i ] [ j ] , d p [ i − 1 ] [ j − k ] + s u m [ i ] [ k ] ) dp[i][j]=max(dp[i][j],dp[i-1][j-k]+sum[i][k]) dp[i][j]=max(dp[i][j],dp[i−1][j−k]+sum[i][k])
a n s = m a x ( d p [ i ] [ j ] , a n s ) 处 理 答 案 即 可 。 ans=max(dp[i][j],ans)处理答案即可。 ans=max(dp[i][j],ans)处理答案即可。

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

Code

#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();
}