ZigZagK的博客
[DP]Codeforces1453F【Even Harder】题解
2020年12月8日 20:14
查看标签

题目概述

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;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!