[luogu1174]打砖块

2018-06-24

lolifamily

题解

贪心 DP

注意：子弹没有的时候不能打有奖励的砖块，打有奖励的砖块可以抽象成借子弹。

w1[i][j] 代表在能借子弹的情况下，第 $𝑖$ 列用了 $𝑗$ 颗子弹能够达到的最高分数， w2 代表不能借子弹的最高分数。

f1[i][j] 代表能借子弹的情况下，从左往右打了 $𝑖$ 列用了 $𝑗$ 颗子弹能够达到的最高分数， f2 代表不借子弹的最高分数。

Problem

题目描述

小红很喜欢玩一个叫打砖块的游戏，这个游戏的规则如下：

在刚开始的时候，有 $𝑛$ 行 $\times$ $𝑚$ 列的砖块，小红有 $𝑘$ 发子弹。

小红每次可以用一发子弹，打碎某一列当前处于这一列最下面的那块砖，并且得到相应的得分。（如图所示）

某些砖块在打碎以后，还可能得到一发子弹的奖励。

最后当所有的砖块都打碎了，或者小红没有子弹了，游戏结束。

小红在游戏开始之前，就已经知道每一块砖在打碎以后的得分，并且知道能不能得到一发奖励的子弹。

小红想知道在这次游戏中她可能的最大得分，可是这个问题对于她来说太难了，你能帮帮她吗？

输入格式

第一行有 $3$ 个正整数， $𝑛$ , $𝑚$ , $𝑘$ 。表示开始的时候，有 $𝑛$ 行 $\times$ $𝑚$ 列的砖块，小红有 $𝑘$ 发子弹。

接下来有 $𝑛$ 行，每行的格式如下： $𝑓 1 𝑐 1 𝑓 2 𝑐 2 𝑓 3 𝑐 3 \dots 𝑓 𝑚 𝑐 𝑚$

其中 $𝑓 𝑖$ 为正整数，表示这一行的第 $𝑖$ 列的砖，在打碎以后的得分。

$𝑐 𝑖$ 为一个字符，只有两种可能， $𝑌$ 或者 $𝑁$ 。 $𝑌$ 表示有一发奖励的子弹， $𝑁$ 表示没有。

所有的数与字符之间用一个空格隔开，行末没有多余的空格。

输出格式

仅一个正整数，表示最大的得分。

输入

1
3 4 2
2
9 N 5 N 1 N 8 N
3
5 N 5 Y 5 N 5 N
4
6 N 2 N 4 N 3 N

输出

1
13

说明 / 提示

对于 $20 %$ 的数据，满足 $1 \leq 𝑛, 𝑚 \leq 5$ ， $1 \leq 𝑘 \leq 10$ ，所有的字符 $𝑐$ 都为 N。

对于 $50 %$ 的数据，满足 $1 \leq 𝑛, 𝑚 \leq 200$ ， $1 \leq 𝑘 \leq 200$ ，所有的字符 $𝑐$ 都为 N。

对于 $100 %$ 的数据，满足 $1 \leq 𝑛, 𝑚 \leq 200$ ， $1 \leq 𝑘 \leq 200$ ，字符 $𝑐$ 可能为 Y。

对于 $100 %$ 的数据，所有的 $𝑓$ 值满足 $1 \leq 𝑓 \leq 10000$ 。

Code

1
#include <iostream>
2
#include <cstdio>
3
#include <cstring>
4
#include <algorithm>
5
using namespace std;
6
int a[205][205],w1[205][205],w2[205][205];
7
int f1[205][205],f2[205][205];
8
bool re[205][205];
9
int main(void)
10
{
11
  int i,j,l,n,m,k,ch,cnt;
12
  scanf("%d%d%d",&n,&m,&k);
13
  for(i=1;i<=n;++i)
14
  {
15
    for(j=1;j<=m;++j)
16
    {
17
      scanf("%d",&a[i][j]);
18
      while(ch=getchar())if(ch=='Y'||ch=='N')break;
19
      re[i][j]=ch=='Y';
20
    }
21
  }
22
  for(j=1;j<=m;++j)
23
  {
24
    cnt=n;
25
    while(cnt&&re[cnt][j])
26
    {
27
      w1[j][0]+=a[cnt][j];--cnt;
28
    }
29
    for(i=1;i<=n&&cnt;++i)//打i发子弹
30
    {
31
      w1[j][i]=w2[j][i]=w1[j][i-1]+a[cnt][j];
32
      --cnt;
33
      while(cnt&&re[cnt][j])
34
      {
35
        w1[j][i]+=a[cnt][j];--cnt;
36
      }
37
    }
38
  }
39
  for(i=1;i<=m;++i)//列
40
  {
41
    for(j=0;j<=k;++j)//子弹
42
    {
43
      for(l=0;l<=j;++l)//当前列使用的子弹数
44
      {
45
        f1[i][j]=max(f1[i][j],f1[i-1][j-l]+w1[i][l]);
46
        if(l<j)f2[i][j]=max(f2[i][j],f2[i-1][j-l]+w1[i][l]);
47
        if(l)f2[i][j]=max(f2[i][j],f1[i-1][j-l]+w2[i][l]);
48
      }
49
    }
50
  }
51
  printf("%d\n",f2[m][k]);
52
  return 0;
53
}