P1174 打砖块

个人推荐 @I_AM_HelloWord 的做法，但感觉他讲的不是很清楚……想了很久终于恍然大悟。提供一种更易懂的说法？

首先，还是只在N处转移。面对Y类砖块，你不需要进行决策。（只要能打，就一定打）

其实这个“借子弹”的说法很容易让人谔谔。子弹本身不会增加，而是打砖块的顺序发生了变化。

比如说，我们原本先打A，但可能此时先打B更优。这时候有一个结论：最后一个打的砖块一定为N类砖块，除非所有砖块已经打完了。 否则，你最后一个打的是Y类砖块，打完之后必定还有子弹。

我们在计算[1,j]列的最优解时，涉及到这些情况：

• 1) 第j列根本不打（直接继承[1,j-1]的状态）
• 2) 最后一发子弹在第j列上（就是之前提过的最后一发打的子弹）
• 3) 最后一发子弹在[1,j-1]列中
• 4) 最后一发子弹不在[1,j]列中（整体上来看，在[j+1,m]中，但与当前状态无关，你只需要知道“不在”）

这些情况是完备的，可以进行状态转移了。

sum1其实对应着当前列是最后一发子弹打的地方，因而以N结尾。sum2则为其余的情况：不是最后一发子弹打的地方，故而最后只能是将Y打到头。

而这个dp(j,k,0/1)其实表示：[1,j]列中，用k发子弹，最后一发子弹是否在[1,j]列中。（0在1不在）

转移1：

dp[j][k][0]=max(dp[j-1][k][0])//这一列一个都不打。

单纯的继承。 转移2：

dp[j][k][0]=max(dp[j-1][k-tot[j][i]][1]+sum1[j][i])

最后一发子弹在[1,j]中，同时也在第j列，故而不在 [1,j-1]中。

转移3：

dp[j][k][0]=max(dp[j-1][k-tot[j][i]][0]+sum2[j][i])

最后一发子弹在[1,j]中，但不在第j列，显然在[1,j-1]中。

转移4：

dp[j][k][1]=max(dp[j-1][k-tot[j][i]][1]+sum2[j][i])

最后一发子弹不在[1,j]中，显然也不再[1,j-1]中，显然也不在第j列。

代码就不放了，以前的题解有。