P10655 「ROI 2017 Day 2」反物质 题解

思路

一眼看上去像一个 dp，但怎么 dp 不太显然。

先考虑爆搜怎么打：最先爆搜获得了 00 个暗物质时的状态，枚举接下来做哪个实验，再枚举这次实验产生了多少暗物质并继续爆搜，对每个实验的结果取 min⁡\min（最坏情况下），再对 nn 个实验的 min⁡\min 值取 max⁡\max（最多能得到多少利润）。

于是我们得到了一个倒着的 dp 式子：fx=max⁡i=1n{min⁡j=x+lix+ri{fj+109×(j−x)}−cj}f_x=\max^n_{i=1}\{\min^{x+r_i}_{j=x+l_i}\{f_j+10^9\times (j-x)\}-c_j\}，要枚举 x,i,jx,i,j 三维，复杂度为 O(a2n)\mathcal{O}(a^2n)，最后答案为 f0f_0。

考虑怎么优化掉一个 aa，把 min⁡\min 里面的式子拆出来，得到 min⁡{fj+109×j}−109×x−cj\min\{f_j+10^9\times j\}-10^9\times x-c_j，发现可以对做每个实验 ii 都来一遍单调队列优化和双指针进行转移，于是这题就做完了，复杂度 O(an)\mathcal{O}(an)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
constexpr int A = 2e6+5,N = 105,D = 1000000000;

ll f[A];
int l[N],r[N],c[N],p[N],n,a;
deque<int> dq[N];

inline ll val(int x){return f[x]+1ll*D*x;}

void solve(){
    read(n,a);
    for(int i=1;i<=n;i++)    read(l[i],r[i],c[i]),p[i] = a;
    for(int i=a;i>=0;i--){
        f[i] = 0;
        for(int j=1;j<=n;j++){
            if(i+r[j]>a)	continue;
            while(p[j]>=i+l[j]){
        		while(!dq[j].empty() && val(p[j])<val(dq[j].back()))	dq[j].pop_back();
        		dq[j].pb_(p[j]);
        		--p[j];
            }
            while(!dq[j].empty() && dq[j].front()>i+r[j])	dq[j].pop_front();
            f[i] = max(f[i],val(dq[j].front())-1ll*D*i-c[j]);
        }
    }
    cout<<f[0];
}