专栏文章

CF1874G

llsj2009Isj2OO9
CF1874G题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqskwp5
此快照首次捕获于
2025/12/04 10:03
3 个月前
此快照最后确认于
2025/12/04 10:03
3 个月前
查看原文

Description

给定一个 DAG，每经过一个点可以获得一些收益，有以下几种点：
  1. 获得一个二元组 (ai,bi)(a_i,b_i)。
  2. 获得一个正整数 xix_i，那可以选取一个 已经获得的 二元组 (aj,bj)(a_j,b_j) 令 aj←aj+xia_j\gets a_j+x_i。
  3. 获得一个正整数 yiy_i，那可以选取一个 已经获得的 二元组 (aj,bj)(a_j,b_j) 令 bj←bj+yib_j\gets b_j+y_i。
  4. 获得一个正整数 wiw_i。
你可以在 最终 选择获得的二元组 (ai,bi)(a_i,b_i) 令 ai←ai×109a_i\gets a_i\times 10^9。
最终获得的总收益 为：∑wiwas gotwi+∑aibi\sum\limits_{w_i\text{was got}} w_i+\sum a_ib_i。
求从 11 走到 nn 的 最大 收益。
1≤n,ai,bi,xi,yi≤2001\le n,a_i,b_i,x_i,y_i\le 200，1≤m≤20001\le m\le 2000，1≤wi≤1061\le w_i\le 10^6。

Solution

在下文中 V=O(ai)=O(bi)=O(xi)=O(yi)V=\mathcal{O}(a_i)=\mathcal{O}(b_i)=\mathcal{O}(x_i)=\mathcal{O}(y_i)。
实际上在 Part 4~6 部分有 V=O(ai)=O(bi)V=\mathcal{O}(a_i)=\mathcal{O}(b_i)，也就是复杂度其实和 xi,yix_i,y_i 无关了。

Part 1

便于讨论，我们先来考虑链的情况。
则首先将 44 类点忽略，因为最后往答案上加一个 ∑wi\sum w_i 即可。
其次注意到 10910^9 相当于一个 ∞\infty，也就是说我们应当将最终获得的二元组序列（在进行 ×109\times 10^9 操作之前）以 max⁡aibi\max a_ib_i 作为第一关键字（记取到 max⁡\max 的点为 tt），∑i≠taibi\sum\limits_{i\ne t}a_ib_i 为第二关键字进行比较。
我们考虑枚举这个取到 max⁡\max 的点 xx。
则对于任意 i>ti>t 的点 ii 如果是 2/32/3 类点则必然将对 tt 进行操作；如果是 11 类点其实就相当于一个 44 类点 wi=aibiw_i=a_ib_i。
则我们仅仅只需要对于前缀 [1,t−1][1,t-1] 做一个没有 ×109\times 10^9 操作的子任务即可。

Part 2

考虑一个特殊性质：没有 33 类点。
也就是我的序列 bb 其实不会发生变化，则每次进行对某个 aia_i 加 xjx_j 操作时我必然会选择在 [1,j−1][1,j-1] 这个前缀 bib_i 取到最大值的 ii。因为 Δanswe=xjbi\Delta \text{answe}=x_jb_i，且这个操作是 没有后效性 的，因为之后对答案权值的新的贡献都和 aia_i 无关了。
同理，在没有 22 类点的情况下，我每次对 bib_i 进行加法操作时也会选取 aa 前缀最大值取到的位置 ii。

Part 3

但是同时存在 2,32,3 类点就很棘手了，因为我的操作变得有后效性了！所以没法直接向上面一样贪心。
但是如果我们现在存在一个上帝视角：我能确定最终 aa 序列的取值！那么根据上面的贪心，我们 对 bb 序列进行加法的位置是确定的。并且我们把对 bb 序列进行加法的位置全部掏出来顺次丢到一个序列 pb1∼kpb_{1\sim k} 里，发现无论 aa 的实际取值如何（也就是哪怕你没有上帝视角你也可以知道），我们总有：
  • ∀i∈[2,k],pbi−1≤pbi\forall i\in[2,k],pb_{i-1}\le pb_i。
因为 前缀最大值取值位置单调不降。
同理我们有 pai−1≤paipa_{i-1}\le pa_i。
发掘这个性质之后，我们注意到进行加法操作（称为 加法点）的位置是不会往前挪的；要么保留原来的，要么到一个新的 (ai,bi)(a_i,b_i) 可能会成为新的加法点，又根据上面 Δanswe\Delta \text{answe} 的形式，我们只关心两个加法点 a,ba,b 的值而不关心具体位置。
则考虑 dp，设：fi,v1,v2,op∈{0,1}f_{i,v_1,v_2,op\in\{0,1\}} 表示考虑 1∼i1\sim i 的点，当前 aa 加法点 jj 有 bj=v1b_j=v_1；当前 bb 加法点 kk 有 ak=v2a_k=v_2；是否有 j=kj=k。转移非常平凡，这里不列出。
朴素实现上有 v1,v2≤nVv_1,v_2\le nV，复杂度即为 O(n3V2)\mathcal{O}(n^3V^2)。

Part 4

考虑 dp 实质，我们的一个暴力就是从前往后遍历所有点，时刻维护所有方案，每个方案的就是两个加法点序列组成的 pair (pa,pb)(pa,pb)，在最终取出权值最大的方案。
我们称一个方案是合法的当且仅当他满足 每个加法点等于最终序列在这个前缀的最大值位置，也就是符合我们从上帝视角来看的贪心。显然最终权值最大的方案是合法的。
而 dp 就是将所有方案划分成若干个等价类，我们宣称 之后的操作对于每个每个等价类内部的所有方案影响是一致的，所以对于每个等价类只保留当前权值最优的方案，复杂度也就变得可以接受了。
然而在 dp 过程中我们不一定保证保留的最优方案必然合法，但是最终不合法的方案必然不优，故而可以不谈论它；其次我们断言：如果一个 fi,bj=v1,ak=v2,opf_{i,b_j=v_1,a_k=v_2,op} 中保留的最优方案是合法的，则必然有 min⁡(v1,v2)≤V\min(v_1,v_2)\le V，否则这个方案必然不是最终答案。
下面给出证明：
更清晰的，我们给出如下引理，并且稍后在谈论引理证明。
  • 如果有 v1,v2>Vv_1,v_2>V，如若该方案转移到 最终的一个合法方案，则最终合法方案有：
    • 存在 p<tp<t 满足 ap,bp>Va_p,b_p>V。
则我们不妨令 t=pt=p，则 (ap,bp)(a_p,b_p) 初值就比 (at,bt)(a_t,b_t) 牛了（这里都考虑了编号 (p,t)(p,t) 对于两者的贡献，不过对于后者先是 00 了），然后 能对 tt 产生贡献的操作必然能对 pp 产生，所以 (ap,bp)(a_p,b_p) 把 (at,bt)(a_t,b_t) 给吊打了，所以 (at,bt)(a_t,b_t) 的最终值（注意这里是跑完了 [1,n][1,n] 的所有操作而不仅仅是 [1,t)[1,t) 的操作）肯定不如 (ap,bp)(a_p,b_p)。
所以 tt 取到当前这个值肯定不是最优，那么这个方案也不是最终答案了。
则接下来仅仅只需要考虑引理证明：
  • 若 j=kj=k，则我们取 p=jp=j 即可。
  • 若 j≠kj\ne k，则 j<kj<k 和 j>kj>k 同理，下面以 j<kj<k 为例：
    • 因为 ak>Va_k>V，说明 kk 是关于 aa 的一个加法点。
      而 关于 aa 的加法点为 bb 的一个前缀最大值位置，且 j<kj<k，所以我们有：
      • bk>bj>Vb_k>b_j>V。
      故而 ak,bk>Va_k,b_k>V，取 p=kp=k 即可。
则有了这个结论，我们 v1/v2v_1/v_2 仅仅只需要开到 O(V)\mathcal{O}(V) 即可。并且我们发现不会有啥先是 v1>Vv_1>V 然后之后 v1<V,v2>Vv_1<V,v_2>V 的情况，因为合法方案下 加法点对应位置的最终值肯定是递增的，也就是之后 v1v_1 肯定还会又大于 VV。
所以不妨直接认为 v1≤Vv_1\le V 即可，再 swap⁡(a,b)\operatorname{swap}(a,b) 跑一遍即可。
复杂度降至 O(n2V2)\mathcal{O}(n^2V^2)。

Part 5

考虑一个「贡献提前计算」的东西，我们不妨 来真正地成为上帝视角：直接对着最终的 aa 序列 dp。
下面为了区分，称最终的 aa 序列为 a′a'。
则我们认为：
  • 11 类点对答案贡献为 ai′bia_i'b_i。
  • 22 类点对答案贡献为 00。
  • 33 类点对答案贡献为 (max⁡j≤iaj′)yi(\max\limits_{j\le i}a_j')y_i。
也就是 把 22 类点的贡献拉到 11 类点直接算了。
如果 ai′>aia_i'>a_i，则 ii 显然就是 aa 序列的一个加法点。则我们设：fi,j,kf_{i,j,k} 表示的是，max⁡p≤iap′=j\max\limits_{p\le i}a_p'=j，上一个加法点 pp 有 k=ap′−apk=a_p'-a_p。参考转移可能会比较清晰：
  • 11 类点：
    • 不是一个加法点：fi−1,j,k+aibi→fi,max⁡(j,ai),kf_{i-1,j,k}+a_ib_i\to f_{i,\max(j,a_i),k}。
    • 是一个加法点（枚举 ai′=xa_i'=x）：fi−1,j,0+xbi→fi,max⁡(j,x),x−aif_{i-1,j,0}+xb_i\to f_{i,\max(j,x),x-a_i}。
  • 22 类点：
    • fi−1,j,k→fi,j,k−xif_{i-1,j,k}\to f_{i,j,k-x_i}。
  • 33 类点：
    • fi−1,j,k+jyi→fi,j,kf_{i-1,j,k}+jy_i\to f_{i,j,k}。
对应到 Part 4，如果我们认为 v2≤Vv_2\le V，则有 k≤j≤Vk\le j\le V，复杂度降至 O(nV2)\mathcal{O}(nV^2)。
复杂度降低的华点在于：我们没有保存 bib_i 的值；为啥不用保存嘞？？？因为保存 bib_i 的值是为了在 22 类点计算贡献，而现在 22 类点的贡献被拉到处理 11 时直接算了；那现在 22 类点还有啥用啊？？？为了 偿还 11 钦定 ai′a_i' 时欠下的加数。
好的，我们现在终于会做链了！！！！！

Part 6

这其实是最简单的一个 Part 了/xk
我们发现处理前缀的这个 dp 可以原封不动的套在 DAG 上，唯一的修改就是 fi−1,∗,∗→fi,∗,∗f_{i-1,*,*}\to f_{i,*,*} 变成了 fu,∗,∗→fv,∗,∗f_{u,*,*}\to f_{v,*,*}，复杂度变成 O(mV2)\mathcal{O}(mV^2)，仍然可以接受。
而对于钦定好 tt 之后后缀的处理，我们需要另一个 dp：记录 gi,j=pair⁡(v1,v2)g_{i,j}=\operatorname{pair}(v_1,v_2) 表示 n→in\to i，j=∑xkj=\sum x_k 时 pair⁡(∑yk,∑wk+∑akbk)\operatorname{pair}(\sum y_k,\sum w_k+\sum a_kb_k) 的 max⁡\max。这个 dp 直接做就是 O(nmV)\mathcal{O}(nmV) 的，可以接受。
最终复杂度 O(mV2)\mathcal{O}(mV^2)。
可能有点 corner case：需要特判不存在 11 类点的情况，这个时候就是再做一个 dp 是关于 wiw_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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...