[luogu1174]打砖块

注意:子弹没有的时候不能打有奖励的砖块,打有奖励的砖块可以抽象成借子弹。

w1[i][j] 代表在能借子弹的情况下,第𝑖列用了𝑗颗子弹能够达到的最高分数, w2 代表不能借子弹的最高分数。

f1[i][j] 代表能借子弹的情况下,从左往右打了𝑖列用了𝑗颗子弹能够达到的最高分数, f2 代表不借子弹的最高分数。

solution-code3192

把图上的每个点拆成两个点,按照老套路连边,把交换的连边流量无穷、代价为 1,其余的边流量为 1、代价为 0,如果满流就输出代价

注意 num1num2 数组的值,这里的 id 不能重复!

solution-code1132

没什么好说的,𝑂(𝑛)的简单 DP。