P1174 打砖块

关于$zhw$神奇的$DP$状态。

• 设$g_{0/1,i,j}$为最后一次是否打在$1$~$i$列中，一共打了$j$颗子弹的最大得分
• 附初始值

g[0][j][dk]=g[0][j-1][dk];
g[1][j][dk]=g[1][j-1][dk];

其中$dk$枚举的是打了几颗子弹，$j$的循环范围为$1$到$m$。

  for(register int i=n;i>=up[j];--i)
    if(dk>=kg[i][j])
        if(!f[i][j])
            g[1][j][dk]=max(g[1][j][dk],g[0][j-1][dk-kg[i][j]]+s[i][j]),
            g[0][j][dk]=max(g[0][j][dk],g[0][j-1][dk-kg[i][j]]+s[i][j]);
        else
            g[1][j][dk]=max(g[1][j][dk],g[1][j-1][dk-kg[i][j]]+s[i][j]),
            g[0][j][dk]=max(g[0][j][dk],g[0][j-1][dk-kg[i][j]]+s[i][j]);

最后一枚子弹如果想要最优的话，一定要打到$N$上（$f_{i,j}=0$），所以假设此时打出了最后一枚子弹，那么它是可以由没有打出最后一枚子弹的状态转移过来的。至于为什么是$j-1$，本列中下面的$N$已经被打完了（$dk-kg_{i,j}$），当然是从前一列转过来阿！如果此时是$Y$的话一定不可能是最后一枚子弹那么假设已经打了最后一枚了，这一枚$Y$只能算是附加的了，不可能再由没有打最后一枚的状态转移过来的了，所以$g_{1,j,dk}$如代码中所示。