2050 Programming Competition – 解题报告

赛题链接:2050.ccpc.io

A – 开场白

模拟。

B – 时间间隔

模拟。

C – 分宿舍

$i\in [0,k]$枚举有多少情侣住情侣间。则可以计算出剩下$(k – i) + n$个男生和$(k – i) + m$个女生。男女不能混住宿。

考虑$x$个同性住宿花费的最小费用,用$f(x, u, v)$表示住$x$个人,假设前面的二人间和三人间都住满,$u$代表可能住不满的二人间的人数,$v$代表可能住不满的三人间的人数,显然有$u \in [0, 2)$,$v \in [0, 3)$。

推得状态转移方程如下:

$$f(i, u, v) = \min \{ f(i – 1, (u – 1) \bmod{2}, v) +ap(u – 1, u), f(i – 1, u, (v – 1) \bmod{3})  + bp(v – 1, v)\}$$

其中$p(x,y)$表示从$x$变到$y$是否需要增加房间,即只有$p(0,1)=1$,其他情况均为零。

则对于每一个$i\in [0,k]$,答案为$i \cdot c + \min \{ f(k – i + m, u, v) \} + \min \{ f(k – i + n, u, v) \}  $,比一个最小的即可。

 

D – PASS

模拟。

E – J

留坑。

说点什么

avatar
50
  Subscribe  
提醒