题解：CF2027C Add Zeros

· · 题解

记忆化搜索 + 图论建模

由于每次操作后是对序列的末尾插入 0，显然后面插入的这些 0 对应的位置 i 一定不满足 a_i = |a| + 1 -i 这个式子，所以后面插入的这些 0 对应的下标 i 完全不需要纳入考虑范围。

也就是说我们只需要考虑一开始数组中存在的下标 i \in [1,n] 进行考虑即可，并且每次操作后 |a| 呈现单调递增，而每次操作也不会让 a_i 的值改变，这意味着每个下标 i 的值最多只会操作一次。

对于题目的 a_i = |a| + 1 -i 这个条件显然可以转化为 |a|=a_i+i-1，当该式成立时会使 |a| \leftarrow |a|+i-1，于是考虑从图论的角度建立一张 DAG 图，即对点 a_i+i-1 向 a_i+i-1+i-1 连一条有向边边，表示当 |a|=a_i+i-1 时 |a| 可以变为 |a|+i-1。

当按照上述规则进行建图后，再从 n 进行 dfs，维护一下 dfs 过程中遇到的最大点权即可。点权就表示数组长度。

由于 a 数组值域很大，需要用 map 来存储。

同时搜索需要记忆化，否则会 TLE。

代码如下：

#define rep(x,y,z) for(int x=y;x<=z;x++)
typedef long long LL;
const int N=3e5+5;
int n;
LL a[N];
map<LL,bool> vis;
map<LL,vector<LL>> E;
LL ans;
void dfs(LL u){
    vis[u]=1;
    ans=max(ans,u);
    for(auto v:E[u]){
        if(vis[v]) continue;
        dfs(v);
    }
}
void solve(){
    vis.clear();
    E.clear();
    cin>>n;
    rep(i,1,n) cin>>a[i];
    rep(i,1,n){
        LL u=a[i]+i-1;
        LL v=u+i-1;
        E[u].push_back(v);
    }
    ans=0;
    dfs(n);
    cout<<ans;
}