华附11.1
好像看到今天纪中没比赛……然后whj没来……我去体测了……
好久没上体育课感觉运动还是挺爽的2333
然而本来想去打球。结果一不给打球二不给补测。日。
逼逼一下今天的题。
bishop
Prob.
给 $ n \times m $ 的矩形。标记一个点会使得它主副对角线的格子都不能被标记。问最多标记多少个点。
$ n, m \le 9 $
Sol.
斜45°放过来,可知每一行每一列只能放一个。
行列不相等时 $ n+m $ 行都可以放。相等时减1. 特判$ n=m=1 $的情况即可。
Code
不存在的。
czybm
Prob.
数轴上有一些点。最开始在 $ v $ 号点上。需要以速度$1$遍历所有点,每个点的花费是等待时间乘价值。
最小化总花费。
$ n \le 1000, d \le 1000, w \le 1000 $
Sol.
区间 dp.
令 $ f_{L, R, 0/1} $ 表示 $ [L, R] $ 编号已被遍历,最后停在左/右边的当前所有妹子总花费最小值。
初值显然。转移显然。答案显然。
吐个槽,只有 optimization 的问题才能叫做动态规划哦。
Code
不存在的。
hop
见 BZOJ 2144.
已阅。
orz Snakes
orz Snak3s
orz Sakura
orz yzw
orz mcw
orz Yang Zhenwei