题目概述

CF1453F

解题报告

考虑路径计数 $cnt_i=\sum_{j=1}^{i-1}[j+a_j\ge i]cnt_j$ ，如果想要 $cnt_n=1$ ，那么一定不存在一个 $cnt_i$ 能从多个 $cnt_j$ 转移过来。

定义 $f_{i,j}$ 表示 $cnt_i=1$ ，且最近的一个 $cnt_j=1$ 的点是 $j$ ，需要删除的最少数量。

$$ f_{i,j}=\min\{f_{j,k}+Count(j+1,i-1)|j+a_j\ge i\ and\ k+a_k<i\}\\ Count(L,R)=\sum_{t=L}^{R}[t+a_t\ge i] $$

但是这样是 $O(n^3)$ 的，不过我们发现可以将所有点按照 $i+a_i$ 排序，然后按照这个排序的顺序求 $f_{j,k}$ 的前缀最小值，这样每次直接每次询问前缀最小值就行了，复杂度降到 $O(n^2)$ ，详见代码。

示例程序

代码写丑了，我是把所有非 $0$ 的元素抠出来做，实际上只要枚举的时候跳过 $0$ 就行了。

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=3000;

int te,n,a[maxn+5],m,p[maxn+5],ID[maxn+5];
int f[maxn+5][maxn+5],pre[maxn+5][maxn+5],ans;

inline bool cmp(const int &i,const int &j) {return p[i]+a[p[i]]<p[j]+a[p[j]];}
int main(){
    for (scanf("%d",&te);te;te--){
        scanf("%d",&n);m=0;
        for (int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            if (a[i] || i==n) p[++m]=i,ID[m]=m;
        }
        sort(ID+1,ID+1+m,cmp);
        for (int i=1;i<=m;i++) for (int j=0;j<=m;j++) f[i][j]=1e9;
        f[1][0]=0;pre[1][0]=0;
        for (int j=1;j<=m;j++) pre[1][j]=min(pre[1][j-1],f[1][ID[j]]);
        for (int i=2,k=0;i<=m;i++){
            while (k<m && p[ID[k+1]]+a[p[ID[k+1]]]<p[i]) k++;
            for (int j=i-1,cnt=0;j;j--)
                if (p[j]+a[p[j]]>=p[i])
                    f[i][j]=pre[j][k]+cnt,cnt++;
            pre[i][0]=f[i][0];
            for (int j=1;j<=m;j++) pre[i][j]=min(pre[i][j-1],f[i][ID[j]]);
        }
        ans=1e9;for (int j=0;j<m;j++) ans=min(ans,f[m][j]);
        printf("%d\n",ans);
    }
    return 0;
}