华附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.