某岛

… : "…アッカリ~ン . .. . " .. .
September 23, 2014

ACM-ICPC World Finals Ekaterinburg 2014

挖坑。

https://gist.github.com/lychees/6b77182120f681429f8f
http://blog.brucemerry.org.za/

Problem B. Buffed Buffet

Brief description:

多重背包、凸背包。

有两类物品可供选择,离散和连续。
对于连续的物品,初始单位容量的价值为 t、单位容量价值损失的速率为 dt。
对于离散的物品,每份物品的容量是 w、初始每份物品的价值为 t、每选择一个物品,下一个件物品价值损失的速率为 dt

问恰好装满 m 容量时的最大价值。

Analysis:

$$! \begin{aligned}g'(i) &= \max_{0 \le j \le i}\big\{ g(j) + \sum_{n=1}^{i-j}(t – (n-1)d\big\}\\&= \max_{0 \le j \le i}\big\{ g(j) + (i-j)t – \frac{(i-j-1)(i-j)}{2}\cdot d\big\}\\&= \max_{0 \le j \le i}\big\{ g(j) + (i-j)t – \frac{i(i-1)+j(j+1)-2ij}{2}\cdot d\big\}\\&= it – \frac{i(i-1)d}{2} + \max_{0 \le j \le i}\big\{ g(j)-\frac{j(j+1)d}{2} – jt + ijd\big\}\\&= it – \frac{i(i-1)d}{2} + \max_{0 \le j \le i}\big\{ h(j) + ijd \big\}\end{aligned}$$

Problem D. Game Strategy

Problem K. Surveillance