题解 P1174 【打砖块】

dalao们的题解永远是我们这群蒟蒻看不懂的。

其实dalao们的转移方程写的不好看，如果按我这么写就比较好理解了。

首先，我们可以有这样一个思路：将一个n上面所有的y都压缩到这个n上面来，因为只要打掉了这个n，上面的y都是免费打掉的。

但请注意，有的时候，我们选择打掉了这个n，却没有子弹来打上面的y了（即打掉这个n的是当前状态的最后一个子弹），于是我们只好将一连串的Y压缩成一个Y，但同时又要注意，有时我们可以将后面列的Y先打掉，那么当前的子弹数并不会减少，我们还是可以打掉当前的N，而我们如果先打掉当前的N，那么就会像上面一样，没有多余的子弹打掉后面的第一个Y了。这时，我们普通的分组背包就会产生后效性。就不对了。

我们稍稍变换一下上面的思路，我们增加一个状态，表示当前列是否在之前的几列中借了子弹。

什么叫借？举个例子吧：

4 2 3 1 N 1 Y

1 Y 1 N

1 Y 1 Y

1 N 1 N

我们设dp[i][j][0/1]表示前i列，共用了j个子弹，第i列0（没借），1（借）最多能够得到的分数。这个借表示借一个子弹给别的地方。

借的子弹是指我们刚好打完一个Y后奖励的那个子弹，我们不接着打后面的N了，而是留着打别的地方的N。

而我们的最后一个子弹，一定打得是个N，如果打得是个Y，我们显然还是可以接着打的。

这时，我们考虑一个借子弹的关系。预处理出一个sum1[i][j]表示第i列打到第j行所能得到的分数，sum2[i][j]表示第i列打到第j行同时把与第j行相连的一连串的Y全部打掉能得到的分数，tot[i][j]表示第i列打到第j行所需的子弹数。

那么首先，

dp[j][k][0]=max(dp[j-1][k][0])//这一列一个都不打。
dp[j][k][0]=max(dp[j-1][k-tot[j][i]][1]+sum1[j][i])//打掉这个N用掉了从前面借来的最后一发子弹
dp[j][k][0]=max(dp[j-1][k-tot[j][i]][0]+sum2[j][i])//打掉一连串的Y后把多余的子弹借给前面列
dp[j][k][1]=max(dp[j-1][k-tot[j][i]][1]+sum2[j][i])//在前面借一个子弹，打完一连串的Y，然后还一个子弹回去。

只要方程理解了，程序就很好打了。

参考代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
template<class T>void ChkMax(T &a,T b){a=a<b?b:a;}
const int INF=0x3f3f3f3f;
const int N=201;
int cur[N],tot[N][N],a[N][N],b[N][N],sum1[N][N],sum2[N][N],dp[N][N][2]={0};
int n,m,k;
int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0' || ch>'9'){if (ch=='-')f=-1;ch=getchar();}
    while ('0'<=ch && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}
int main(){
    n=read(),m=read(),k=read();
    for (int i=n;i>=1;i--)
        for (int j=1;j<=m;j++){
            a[i][j]=read();
            char cmd=getchar();
            while (cmd<'A' || cmd>'Z')cmd=getchar();
            if (cmd=='Y')b[i][j]=1;
        }
    int ans=0;
    for (int j=1;j<=m;j++){
        for (int i=1;i<=n;i++){
            if (!b[i][j]){cur[j]=i;break;}
            ans+=a[i][j];
        }
    }
    for (int j=1;j<=m;j++)
        for (int i=cur[j];i<=n;i++)
            sum2[j][i]=sum1[j][i]=sum1[j][i-1]+a[i][j];
    for (int j=1;j<=m;j++){
        tot[j][cur[j]]=1;
        for (int i=cur[j];i<=n;i++){
            int idx=i;
            while (b[idx+1][j])idx++;
            sum2[j][i]+=sum1[j][idx]-sum1[j][i];
            tot[j][idx+1]=tot[j][i]+1;
            i=idx;
        }
    }
    for (int j=0;j<=m;j++)
        dp[j][0][0]=-INF;
    for (int j=1;j<=m;j++){
        for (int tk=1;tk<=k;tk++){
            dp[j][tk][0]=dp[j-1][tk][0];
            dp[j][tk][1]=dp[j-1][tk][1];
            for (int i=cur[j];i<=n;i++)
                if (!b[i][j] && tk>=tot[j][i]){
                    ChkMax(dp[j][tk][0],dp[j-1][tk-tot[j][i]][1]+sum1[j][i]);
                    ChkMax(dp[j][tk][0],dp[j-1][tk-tot[j][i]][0]+sum2[j][i]);
                    ChkMax(dp[j][tk][1],dp[j-1][tk-tot[j][i]][1]+sum2[j][i]);
                }
        }
    }
    printf("%d",dp[m][k][0]+ans);
    return 0;
}