P1174 打砖块 题解

· · 题解

0x00 思路

此题让我十分的销魂（销魂：极度悲伤）

先看题。

小红很喜欢玩一个叫打砖块的游戏，这个游戏的规则如下在刚开始的时候，有 n 行 \times m 列的砖块，小红有 k 发子弹。小红每次可以用一发子弹，打碎某一列当前处于这一列最下面的那块砖，并且得到相应的得分。某些砖块在打碎以后，还可能将得到一发子弹的奖励。最后当所有的砖块都打碎了，或者小红没有子弹了，游戏结束。小红在游戏开始之前，就已经知道每一块砖在打碎以后的得分，并且知道能不能得到一发奖励的子弹。小红想知道在这次游戏中她可能的最大得分，可是这个问题对于她来说太难了，你能帮帮她吗？

回答问题：不能。看完题目会有一个明显的区间 dp 思路,我们很明显可以定义一个 dp 数组来存储前 i 列用 j 个子弹最多所得分数。

0x01 初始化

由于我们需要用到每一列用 i 颗子弹可以得到的分数（没有最大，因为分数唯一），为节省时间所以我们准备算出它们。

coding

注：(非最终答案)

for(i=1;i<=m;i++)//列
{
    for(j=1,w=n;j<=k&&w>0;j++,w--)//子弹未消耗完（j），砖块未打完（w）
    {
        if(c[w][i]=='Y')//Y不消耗子弹
            sum[i][--j]+=f[w][i];
        else
            sum[i][j]=sum[i][j-1]+f[w][i];
    }
}

好了，这个初始化出来了你就可以得一些分了（全是 N 的情况）。

只想得部分分的同学可直接跳转0x02。

那么为了得 100pts 的谷友们，你们可以先测试一下这组数据：（输出 8）

3 3 3
1 Y 1 Y 1 Y
1 N 1 N 1 N
1 Y 1 Y 1 Y

你会发现如果你的初始化是如上的初始化时，你的程序会输出 9 。可你只能得到 8 。

原因很简单，当你在打最后一块砖（一定是 Y）时你没子弹了！但是由于程序自动认为打 Y 不消耗子弹，所以你的程序就将输出 9 。

为了得到满分，可以思考 Y 和 N 的不同，既然这是 2 种不同的砖块，那么可以用 2 个数组来分别记录最后打到的砖是 Y 和 N 的得分，就阻止了上述情况的出现。

那么为了防止冷不丁在这一列中出现 Y 而打得你措手不及，你的记录 Y 的数组仍然要记录 N 的状态。

code

注：最终代码

for(i=1;i<=m;i++)
{
    for(j=1,w=n;j<=min(n,k)&&w>0;j++,w--)//j,w意义同上
    {
        if(c[w][i]=='Y') //根据前文，dy为最后打'Y',dn为最后打'N'
            dy[i][--j]+=f[w][i];
        else
            dy[i][j]=dy[i][j-1]+f[w][i],dn[i][j]=dy[i][j];
    }
}

0x02 区间 dp

仍然分 2 部分，前面是部分分，后面是满分。

定义数组 dp[i][j] : 用 j 颗子弹打前 i 列砖块的最大得分。

那么由于是区间 dp，所以假设用了 l 颗子弹来打第 i 列砖，那么前 i-1 列就用了 j-l 颗子弹，求得最大值即可。

coding

for(i=1;i<=m;i++)//第i列
{
    for(j=1;j<=k;j++)//前i列共用j颗子弹
    {
        for(l=0;l<=j;l++)//当前列使用的子弹数
            dp[i][j]=max(dp[i-1][l]+sum[i][j-l],dp[i][j]);
    }
}

（对于部分分）End

你会发现你根本没有办法得满分（状态转移如上的话），于是你就会再次思考：子弹打在 Y 上和在 N 上有什么区别？

由于打 Y 会附赠一颗子弹，那么相当于没有使用子弹，但是打在 N 上就没有这个反馈，因此最后一颗子弹一定打在 N 砖块上。那么由于顺序不定，所以你可以先打后面再返回来打前面，所以这是最后一颗子弹有 3 种打法：在此列使用、在前面的列使用或在之后使用。

仍然是 3 重循环，分别表示前 i 列用 j 颗子弹，且当前列使用 l 颗子弹。

那么我们里面的状态转移就会发生改变：先定义 2 个 dp 数组，分别表示在前 i 列没有用光 j 颗子弹（dp1），在前 i 列用光了 j 颗子弹（dp2）。

根据我们上面的推论，这里就有 2 种情况。

在最后输出的时候输出 dp2[m][k] 就好了，因为它代表在前 m 列用了 k 颗子弹最多所得分数（你本来就只有 m 列 k 颗子弹好吧）

结束语

说实话，这道题挺恶心的，因为它的思维量很大，所以很难去想怎么做。就给你一种：我知道它是区间 dp，但是就是做不出来的无奈心情。

但是不得不说，这个 dp 题真的挺好，不做可惜了QWQ。

（代码就不用给了吧……都已经放题解里了……）