AT_abc325_f Sensor Optimization Dilemma 题解

发布时间 2023-10-31 10:18:35作者: RainPPR

AT_abc325_f Sensor Optimization Dilemma 题解

Date 20231025:修复手滑公式 \(\min\)\(\max\) 写反了。

动态规划。类似背包问题。

朴素算法

\((x,y)\) 表示使用 \(x\) 个 (1) 传感器、\(y\) 个 (2) 号传感器。

\(f(t,i,j)\) 表示覆盖前 \(t\) 个区间,使用 \((i,j)\) 传感器,是否可行。

枚举第 \(t\) 个区间使用 \((p,q)\) 传感器:

\[\boxed{f(t,i,j)=\max\{f(t-1,i-p,j-q)\times[pL_1+qL_2\ge D_i]\}} \]

状态数 \(NK_1K_2\),转移量 \(K_1K_2\),因此,总时间复杂度为 \(\mathcal{O}(N{K_1}^2{K_2}^2)\),大约为 \(10^{14}\),不可过。

考虑优化

每个状态只记录 \(0/1\) 是不是有点浪费呢?

于是就可以考虑一个经典的状态设计优化,将一个状态放在结果里。

我们可以将 \(f(t,i,j)\)\(j\) 放在结果里。

具体的,设 \(f(t,i)\) 表示考虑前 \(t\) 个区间,使用 \(i\) 个 (1) 传感器,最少要使用的 (2) 传感器数量。

明显的,结果为 \(\min\limits_{i=1}^{K_1}\{f(n,i)\}\space(f(n,i)\le K_2)\).

其实这个式子也是有单调性的,但是由于 \(K\le10^3\),我们可以不用考虑。

考虑转移,也不复杂,与朴素算法类似,我们枚举第 \(t\) 个区间使用 \(k\)\((1)\) 传感器,那么给 \((2)\) 号传感器留了 \(\max(D_i-kL_1,0)\) 的空间:

\[\boxed{f(i,j)=\min\limits_{k=0}^j\Big\{f(i-1,j-k)+\Big\lceil\dfrac{\max(D_i-kL_1,0)}{L_2}\Big\rceil\Big\}} \]

状态数 \(NK_1\),转移量 \(K_1\),因此,总时间复杂度为 \(\mathcal{O}(N{K_1}^2)\),大约为 \(10^8\),可过。

代码:https://atcoder.jp/contests/abc325/submissions/46898766