P1174 打砖块
个人推荐 @I_AM_HelloWord 的做法,但感觉他讲的不是很清楚……想了很久终于恍然大悟。提供一种更易懂的说法?
首先,还是只在N处转移。面对Y类砖块,你不需要进行决策。(只要能打,就一定打)
其实这个“借子弹”的说法很容易让人谔谔。子弹本身不会增加,而是打砖块的顺序发生了变化。
比如说,我们原本先打A,但可能此时先打B更优。这时候有一个结论:最后一个打的砖块一定为N类砖块,除非所有砖块已经打完了。 否则,你最后一个打的是Y类砖块,打完之后必定还有子弹。
我们在计算
- 1) 第j列根本不打(直接继承
[1,j-1] 的状态) - 2) 最后一发子弹在第j列上(就是之前提过的最后一发打的子弹)
- 3) 最后一发子弹在
[1,j-1] 列中 - 4) 最后一发子弹不在
[1,j] 列中(整体上来看,在[j+1,m] 中,但与当前状态无关,你只需要知道“不在”)
这些情况是完备的,可以进行状态转移了。
sum1其实对应着当前列是最后一发子弹打的地方,因而以N结尾。sum2则为其余的情况:不是最后一发子弹打的地方,故而最后只能是将Y打到头。
而这个
转移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])
最后一发子弹在
转移3:
dp[j][k][0]=max(dp[j-1][k-tot[j][i]][0]+sum2[j][i])
最后一发子弹在
转移4:
dp[j][k][1]=max(dp[j-1][k-tot[j][i]][1]+sum2[j][i])
最后一发子弹不在
代码就不放了,以前的题解有。