CF1874G
lsj2009
·
·
题解
Description
给定一个 DAG，每经过一个点可以获得一些收益，有以下几种点：
-
获得一个二元组 (a_i,b_i)。
-
获得一个正整数 x_i，那可以选取一个 已经获得的 二元组 (a_j,b_j) 令 a_j\gets a_j+x_i。
-
获得一个正整数 y_i，那可以选取一个 已经获得的 二元组 (a_j,b_j) 令 b_j\gets b_j+y_i。
-
获得一个正整数 w_i。
你可以在 最终 选择获得的二元组 (a_i,b_i) 令 a_i\gets a_i\times 10^9。
最终获得的总收益 为：\sum\limits_{w_i\text{was got}} w_i+\sum a_ib_i。
求从 1 走到 n 的 最大 收益。
## Solution
在下文中 $V=\mathcal{O}(a_i)=\mathcal{O}(b_i)=\mathcal{O}(x_i)=\mathcal{O}(y_i)$。
实际上在 Part 4~6 部分有 $V=\mathcal{O}(a_i)=\mathcal{O}(b_i)$，也就是复杂度其实和 $x_i,y_i$ 无关了。
#### Part 1
便于讨论，我们先来考虑链的情况。
则首先将 $4$ 类点忽略，因为最后往答案上加一个 $\sum w_i$ 即可。
其次注意到 $10^9$ 相当于一个 $\infty$，也就是说我们应当将最终获得的二元组序列（在进行 $\times 10^9$ 操作之前）以 $\max a_ib_i$ 作为第一关键字（记取到 $\max$ 的点为 $t$），$\sum\limits_{i\ne t}a_ib_i$ 为第二关键字进行比较。
我们考虑枚举这个取到 $\max$ 的点 $x$。
则对于任意 $i>t$ 的点 $i$ 如果是 $2/3$ 类点则必然将对 $t$ 进行操作；如果是 $1$ 类点其实就相当于一个 $4$ 类点 $w_i=a_ib_i$。
**则我们仅仅只需要对于前缀 $[1,t-1]$ 做一个没有 $\times 10^9$ 操作的子任务即可**。
### Part 2
考虑一个特殊性质：没有 $3$ 类点。
也就是我的序列 $b$ 其实不会发生变化，则每次进行对某个 $a_i$ 加 $x_j$ 操作时我必然会选择**在 $[1,j-1]$ 这个前缀 $b_i$ 取到最大值的** $i$。因为 $\Delta \text{answe}=x_jb_i$，且这个操作是 **没有后效性** 的，因为之后对答案权值的新的贡献都和 $a_i$ 无关了。
同理，在没有 $2$ 类点的情况下，我每次对 $b_i$ 进行加法操作时也会选取 $a$ **前缀最大值取到的位置** $i$。
### Part 3
但是同时存在 $2,3$ 类点就很棘手了，因为我的操作变得有后效性了！所以没法直接向上面一样贪心。
但是如果我们现在存在一个上帝视角：我能确定最终 $a$ 序列的取值！那么根据上面的贪心，我们 **对 $b$ 序列进行加法的位置是确定的**。并且我们把对 $b$ 序列进行加法的位置全部掏出来顺次丢到一个序列 $pb_{1\sim k}$ 里，发现无论 $a$ 的实际取值如何（也就是哪怕你没有上帝视角你也可以知道），我们总有：
- $\forall i\in[2,k],pb_{i-1}\le pb_i$。
因为 **前缀最大值取值位置单调不降**。
同理我们有 $pa_{i-1}\le pa_i$。
发掘这个性质之后，我们注意到进行加法操作（称为 **加法点**）的位置是不会往前挪的；**要么保留原来的，要么到一个新的 $(a_i,b_i)$ 可能会成为新的加法点**，又根据上面 $\Delta \text{answe}$ 的形式，我们只关心两个加法点 $a,b$ 的值而不关心具体位置。
则考虑 dp，设：$f_{i,v_1,v_2,op\in\{0,1\}}$ 表示考虑 $1\sim i$ 的点，当前 $a$ 加法点 $j$ 有 $b_j=v_1$；当前 $b$ 加法点 $k$ 有 $a_k=v_2$；是否有 $j=k$。转移非常平凡，这里不列出。
朴素实现上有 $v_1,v_2\le nV$，复杂度即为 $\mathcal{O}(n^3V^2)$。
### Part 4
考虑 dp 实质，我们的一个暴力就是从前往后遍历所有点，时刻维护所有方案，每个方案的就是两个加法点序列组成的 pair $(pa,pb)$，在最终取出权值最大的方案。
我们称一个方案是合法的当且仅当他满足 **每个加法点等于最终序列在这个前缀的最大值位置**，也就是符合我们从上帝视角来看的贪心。显然最终权值最大的方案是合法的。
而 dp 就是将所有方案划分成若干个等价类，我们宣称 **之后的操作对于每个每个等价类内部的所有方案影响是一致的**，所以对于每个等价类只保留当前权值最优的方案，复杂度也就变得可以接受了。
然而在 dp 过程中我们不一定保证保留的最优方案必然合法，但是最终不合法的方案必然不优，故而可以不谈论它；其次我们断言：**如果一个 $f_{i,b_j=v_1,a_k=v_2,op}$ 中保留的最优方案是合法的，则必然有 $\min(v_1,v_2)\le V$，否则这个方案必然不是最终答案**。
下面给出证明：
> 更清晰的，我们给出如下引理，并且稍后在谈论引理证明。
>
> - 如果有 $v_1,v_2>V$，如若该方案转移到 **最终的一个合法方案**，则最终合法方案有：
>
> - 存在 $p<t$ 满足 $a_p,b_p>V$。
>
> 则我们不妨令 $t=p$，则 $(a_p,b_p)$ 初值就比 $(a_t,b_t)$ 牛了（这里都考虑了编号 $(p,t)$ 对于两者的贡献，不过对于后者先是 $0$ 了），然后 **能对 $t$ 产生贡献的操作必然能对 $p$ 产生**，所以 $(a_p,b_p)$ 把 $(a_t,b_t)$ 给吊打了，所以 $(a_t,b_t)$ 的最终值（注意这里是跑完了 $[1,n]$ 的所有操作而不仅仅是 $[1,t)$ 的操作）肯定不如 $(a_p,b_p)$。
>
> **所以 $t$ 取到当前这个值肯定不是最优，那么这个方案也不是最终答案了**。
>
> 则接下来仅仅只需要考虑引理证明：
>
> - 若 $j=k$，则我们取 $p=j$ 即可。
>
> - 若 $j\ne k$，则 $j<k$ 和 $j>k$ 同理，下面以 $j<k$ 为例：
>
> - 因为 $a_k>V$，说明 $k$ 是关于 $a$ 的一个加法点。
>
> 而 **关于 $a$ 的加法点为 $b$ 的一个前缀最大值位置**，且 $j<k$，所以我们有：
>
> - $b_k>b_j>V$。
>
> 故而 $a_k,b_k>V$，取 $p=k$ 即可。
则有了这个结论，我们 $v_1/v_2$ 仅仅只需要开到 $\mathcal{O}(V)$ 即可。并且我们发现不会有啥先是 $v_1>V$ 然后之后 $v_1<V,v_2>V$ 的情况，因为合法方案下 **加法点对应位置的最终值肯定是递增的**，也就是之后 $v_1$ 肯定还会又大于 $V$。
所以不妨直接认为 $v_1\le V$ 即可，再 $\operatorname{swap}(a,b)$ 跑一遍即可。
复杂度降至 $\mathcal{O}(n^2V^2)$。
### Part 5
考虑一个「**贡献提前计算**」的东西，我们不妨 **来真正地成为上帝视角**：直接对着最终的 $a$ 序列 dp。
下面为了区分，称最终的 $a$ 序列为 $a'$。
则我们认为：
- $1$ 类点对答案贡献为 $a_i'b_i$。
- $2$ 类点对答案贡献为 $0$。
- $3$ 类点对答案贡献为 $(\max\limits_{j\le i}a_j')y_i$。
也就是 **把 $2$ 类点的贡献拉到 $1$ 类点直接算了**。
如果 $a_i'>a_i$，则 $i$ 显然就是 $a$ 序列的一个加法点。则我们设：$f_{i,j,k}$ 表示的是，$\max\limits_{p\le i}a_p'=j$，上一个加法点 $p$ 有 $k=a_p'-a_p$。参考转移可能会比较清晰：
- $1$ 类点：
- 不是一个加法点：$f_{i-1,j,k}+a_ib_i\to f_{i,\max(j,a_i),k}$。
- 是一个加法点（枚举 $a_i'=x$）：$f_{i-1,j,0}+xb_i\to f_{i,\max(j,x),x-a_i}$。
- $2$ 类点：
- $f_{i-1,j,k}\to f_{i,j,k-x_i}$。
- $3$ 类点：
- $f_{i-1,j,k}+jy_i\to f_{i,j,k}$。
对应到 Part 4，如果我们认为 $v_2\le V$，则有 $k\le j\le V$，复杂度降至 $\mathcal{O}(nV^2)$。
复杂度降低的华点在于：**我们没有保存 $b_i$ 的值**；为啥不用保存嘞？？？因为保存 $b_i$ 的值是为了在 $2$ 类点计算贡献，而现在 $2$ 类点的贡献被拉到处理 $1$ 时直接算了；那现在 $2$ 类点还有啥用啊？？？为了 **偿还 $1$ 钦定 $a_i'$ 时欠下的加数**。
好的，我们现在终于会做链了！！！！！
### Part 6
这其实是最简单的一个 Part 了/xk
我们发现处理前缀的这个 dp 可以原封不动的套在 DAG 上，唯一的修改就是 $f_{i-1,*,*}\to f_{i,*,*}$ 变成了 $f_{u,*,*}\to f_{v,*,*}$，复杂度变成 $\mathcal{O}(mV^2)$，仍然可以接受。
而对于钦定好 $t$ 之后后缀的处理，我们需要另一个 dp：记录 $g_{i,j}=\operatorname{pair}(v_1,v_2)$ 表示 $n\to i$，$j=\sum x_k$ 时 $\operatorname{pair}(\sum y_k,\sum w_k+\sum a_kb_k)$ 的 $\max$。这个 dp 直接做就是 $\mathcal{O}(nmV)$ 的，可以接受。
最终复杂度 $\mathcal{O}(mV^2)$。
可能有点 corner case：需要特判不存在 $1$ 类点的情况，这个时候就是再做一个 dp 是关于 $w_i$ 的点权最长路即可。
## Code
```cpp
#include<bits/stdc++.h>
#define int long long
// #pragma GCC optimize(3,"Ofast","inline")
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ll long long
#define bint __int128
#define ull unsigned long long
#define uint unsigned int
#define ld double
#define PII pair<int,int>
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
#define pcnt(x) __builtin_popcount(x)
#define lg(x) (31-__builtin_clz(x))
using namespace std;
void file_IO() {
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
}
bool M1;
const int INF=0x3f3f3f3f;
const ll INFLL=0x3f3f3f3f3f3f3f3f;
const ld eps=1e-9;
const int N=2e2+5,M=2e3+5,NV=4e4+5;
int op[N],a[N],b[N],mx,n,m;
int head1[N],len1,head2[N],len2;
struct node {
int to,nxt;
}; node edge1[M],edge2[M];
void add_edge1(int u,int v) {
edge1[++len1]={v,head1[u]}; head1[u]=len1;
}
void add_edge2(int u,int v) {
edge2[++len2]={v,head2[u]}; head2[u]=len2;
}
int f[2][N][N][N];
void solve1(int pp) {
rep(i,1,n) {
rep(j,0,mx) {
rep(k,0,mx)
f[pp][i][j][k]=-INF;
}
}
f[pp][1][0][0]=0;
rep(u,1,n) {
for(int i=head1[u];i;i=edge1[i].nxt) {
int v=edge1[i].to;
if(op[v]==1) {
rep(j,0,mx) {
rep(k,0,mx)
chkmax(f[pp][v][max(j,a[v])][k],f[pp][u][j][k]+a[v]*b[v]);
rep(p,a[v],mx)
chkmax(f[pp][v][max(j,p)][p-a[v]],f[pp][u][j][0]+p*b[v]);
}
} else if(op[v]==2) {
rep(j,0,mx) {
rep(k,0,mx) {
chkmax(f[pp][v][j][k],f[pp][u][j][k]);
if(k>=a[v])
chkmax(f[pp][v][j][k-a[v]],f[pp][u][j][k]);
}
}
} else if(op[v]==3) {
rep(j,0,mx) {
rep(k,0,mx)
chkmax(f[pp][v][j][k],f[pp][u][j][k]+j*a[v]);
}
} else {
rep(j,0,mx) {
rep(k,0,mx)
chkmax(f[pp][v][j][k],f[pp][u][j][k]+a[v]);
}
}
}
}
}
PII g[N][NV];
int h[N];
void solve2() {
rep(i,1,n) {
rep(j,0,n*mx)
g[i][j]=make_pair(-INF,-INF);
}
g[n][0]=make_pair(0,0);
per(u,n,1) {
for(int i=head2[u];i;i=edge2[i].nxt) {
int v=edge2[i].to;
if(op[v]==2) {
rep(j,0,n*mx) {
chkmax(g[v][j],g[u][j]);
if(j>=a[v])
chkmax(g[v][j],g[u][j-a[v]]);
}
} else if(op[v]==3) {
rep(j,0,n*mx)
chkmax(g[v][j],make_pair(g[u][j].first+a[v],g[u][j].second));
} else {
int val=op[v]==0? 0:(op[v]==1? a[v]*b[v]:a[v]);
rep(j,0,n*mx)
chkmax(g[v][j],make_pair(g[u][j].first,g[u][j].second+val));
}
chkmax(h[v],h[u]+(op[v]==4)*a[v]);
}
}
}
void solve() {
scanf("%lld%lld",&n,&m);
rep(i,1,n) {
scanf("%lld",&op[i]);
if(op[i]==1) {
scanf("%lld%lld",&a[i],&b[i]);
chkmax(mx,a[i]);
chkmax(mx,b[i]);
} else if(op[i]) {
scanf("%lld",&a[i]);
if(op[i]!=4)
chkmax(mx,a[i]);
}
}
while(m--) {
int u,v;
scanf("%lld%lld",&u,&v);
add_edge1(u,v);
add_edge2(v,u);
}
solve1(0);
rep(i,1,n) {
if(op[i]==1)
swap(a[i],b[i]);
else if(op[i]==2)
op[i]=3;
else if(op[i]==3)
op[i]=2;
}
solve1(1);
rep(i,1,n) {
if(op[i]==1)
swap(a[i],b[i]);
else if(op[i]==2)
op[i]=3;
else if(op[i]==3)
op[i]=2;
}
solve2();
int res=h[1],t=1000000000;
rep(v,1,n) {
if(op[v]==1) {
int mxx=-INFLL;
rep(j,0,mx)
chkmax(mxx,max(f[0][v][j][0],f[1][v][j][0]));
mxx-=a[v]*b[v];
rep(j,0,n*mx) {
if(g[v][j].first>=0)
chkmax(res,mxx+t*(a[v]+j)*(b[v]+g[v][j].first)-a[v]*b[v]+g[v][j].second);
}
}
}
printf("%lld\n",res);
}
bool M2;
// g++ CF1874G.cpp -std=c++14 -Wall -O2 -o CF1874G
signed main() {
// file_IO();
int testcase=1;
// scanf("%d",&testcase);
while(testcase--)
solve();
debug("used time = %dms\n",(signed)(1000*clock()/CLOCKS_PER_SEC));
debug("used memory = %dMB\n",(signed)((&M1-&M2)/1024/1024));
return 0;
}
```