LGOJ P1174 | 打砖块

Portal

假设所以砖块都为 NN,无论打的顺序如何对后面的砖块都没有影响,这就是一个普通的多重背包。于是我们可以先预处理出在第 ii 列打 jj 发子弹的得分 p[i][j],显然我们可以定义 a[i][v] 为在前 ii 列打 vv 发子弹的最大得分并直接写出状态转移方程 ai,v=max{ai,v,ai1,vk+pi,j}a_{i,v}=\max {a_{i,v},a_{i-1,v-k}+p_{i,j}}。也就是在前 ii 列的砖打 vv 发,如果从前 i1i-1 列拿一发子弹打第 ii 列能得更多分则转移。于是骗到了 50 分 like this

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>
#include <algorithm>
int main() {
const int N=201;
int n,m,k,w[N][N];char c[N][N];
static int a[N][N],p[N][N];
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
scanf("%d %c",&w[i][j],&c[i][j]);
for(int i=1;i<=m;++i)
for(int j=1,v=n;j<=k&&j<=n;++j,--v)
p[i][j]=p[i][j-1]+w[v][i];
for(int i=1;i<=m;++i)
for(int v=1;v<=k;++v)
for(int j=0;j<=v&&j<=n;++j)
a[i][v]=std::max(a[i][v],a[i-1][v-j]+p[i][j]);
printf("%d",a[m][k]);
return 0;
}

如果不是所有的砖块为 N,那么问题就是一个有局部后效性的多重背包。我们可以定义“白嫖”为在遇到若干个连续的 Y 砖块时不花费子弹全部打掉。那么 py[i][j] pn[i][j] ay[i][v] an[i][v] 分别为在第 ii 列打 jj 发并白嫖或不白嫖的最大得分和在前 ii 列打 vv 发并白嫖或不白嫖的最大得分。当打 jj 发后遇到 nn 个连续 Y 砖块时 py 会不花子弹直接将所有分数加入 py[i][j] 中,而 pn[i][j] 是将这若干个 Y 砖块缩合成一个分数为 i=ii+nwi\sum\limits_{i=i}^{i+n}w_i 的 N 砖块。

可以直接用下面的方法进行预处理:

1
2
3
4
5
6
7
for(int i=1,t=n;i<=m;++i,t=n) {
for(;t>0&&c[t][i]=='Y';--t) py[i][0]+=w[t][i];
for(int j=1;j<=n&&t>0;++j) {
pn[i][j]=py[i][j-1]+w[t--][i];py[i][j]=pn[i][j];
for(;t>0&&c[t][i]=='Y';--t) py[i][j]+=w[t][i];
}
}

dp 部分大体不变只需要分别对白嫖和不白嫖的情况分别进行 dp 再取最大值即可。

1
2
3
4
5
6
7
for(int i=1;i<=m;++i)
for(int v=0;v<=k;++v)
for(int j=0;j<=n&&j<=v;++j) {
an[i][v]=std::max(an[i-1][v-j]+py[i][j],an[i][v]);
if(j<v) ay[i][v]=std::max(ay[i-1][v-j]+py[i][j],ay[i][v]);
if(j>0) ay[i][v]=std::max(an[i-1][v-j]+pn[i][j],ay[i][v]);
}

然后就 AC 了

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
#include <cstdio>
#include <algorithm>
using std::max;
int main() {
const int N=201;
int n,m,k,w[N][N];char c[N][N];
static int py[N][N],pn[N][N],ay[N][N],an[N][N];
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
scanf("%d %c",&w[i][j],&c[i][j]);
for(int i=1,t=n;i<=m;++i,t=n) {
for(;t>0&&c[t][i]=='Y';--t) py[i][0]+=w[t][i];
for(int j=1;j<=n&&t>0;++j) {
pn[i][j]=py[i][j-1]+w[t--][i];py[i][j]=pn[i][j];
for(;t>0&&c[t][i]=='Y';--t) py[i][j]+=w[t][i];
}
}
for(int i=1;i<=m;++i)
for(int v=0;v<=k;++v)
for(int j=0;j<=n&&j<=v;++j) {
an[i][v]=max(an[i-1][v-j]+py[i][j],an[i][v]);
if(j<v) ay[i][v]=max(ay[i-1][v-j]+py[i][j],ay[i][v]);
if(j>0) ay[i][v]=max(an[i-1][v-j]+pn[i][j],ay[i][v]);
}
printf("%d",ay[m][k]);
return 0;
}

Download

本站所有原创内容采用 CC-BY-NC-ND 4.0 International 协议进行许可,附加条款亦可能应用。部分非原创内容版权为 上海アリス幻楽団黄昏フロンティア 等同人创作者所有。

题解 OI

评论

您需要成为穿墙的邪仙以加载 Disqus。