250p TheMoviesLevelOneDivOne
电影院有n行m列的座位, 有一些已经被预订了. 求在剩下的座位中, 选出同行且相邻的两个座位的方案数.
可以按行列将已预订的座位排序, 然后顺便扫一遍, 算出相邻两个被预订座位之间的方案数. 最后累加.
也可以用个set记录不能使用的方案, 再用没有预订座位的情况下的总方案数减去之.

500p TheMoviesLevelTwoDivOne
若干部电影, 每部电影有一个加血的时间点. 人看电影, 每看一分钟掉一点血. 血掉到0就结束. 问怎样按排顺序使看的电影部数最多. 如果总部数相同, 取字典序最小的解输出.
只有20部电影, 状态DP即可.
为保证字典序, 可以从后往前DP, 这样每次转移时新加入的电影都是当前最先看的, 保证它先择的是最小的, 即能保证字典序最小.

[DP]

1000p TheMoviesLevelThreeDivOne
若干部电影, A和B两人看每部电影的时间分别是A[i], B[i]. 初始安排, 要依次把第1,2,..,n部电影放入A或B的待看队列的队尾. A和B各自开始看自己队列中的电影, 看完一部后, 如果这是另一个人没看过的, 就加入它的队列中. 如果期间某人列队空了, 那么他就结束, 再也不看新电影了. 问有多少种初始安排方法, 能使A和B都能看完所有电影.
首先肯定不会出现一种安排使得A和B都卡. 因为A卡肯定发生在A看完他所有的电影之后, 且此时B没看完自己的, 所以B肯定不会卡.
这样就可以用总方案数2^N分别减去A卡的和B卡的方案数. 考虑A卡的情况. 假设A那一整坨东西的时长是sumA, B的第一个东西是tb1, 则A卡的条件是 sumA-tb1<0. 否则B看完tb1后把ta1加在sumA后面, 这时卡的条件是(sumA+ta1)-(tb1+tb2)<0. 依此, 如果在这过程中任意一次卡的条件符合, 那么后续怎么安排都是卡的. 于是用一维状态记录目前为止出现过的最小的X-Y, min, 还要一维记录当前的X-Y, cur, 以转移用. 转移时, 如果把当前电影放进A, 那么min和cur都增加A[i], 因为sumA增加了. 如果放进B, 那么用cur和B[i]来计算新的cur和min.
hint. cur=当前所有电影的A[i]的和-B中电影的B[i]的和, 新的min=除了新放的电影外所有放过的电影的A[i]的和-包括新电影在内的B中电影的B[i]的和.

ps. 1000的DP都很YD啊...

[DP]