题解-CF1453F Even Harder

题面

CF1453F Even Harder

有一行 \(n\) 个鸽子,每个鸽子有个跳跃能力 \(a_i\),表示站在这个鸽子上的人可以跳到每个满足 \(i+1\le j< i+a_i\) 的第 \(j\) 个鸽子。现在有个人在第 \(1\) 只鸽子身上,他的目标是跳到第 \(n\) 子鸽子身上。请问您最少杀死几只鸽子(使 \(a_i\) 变成 \(0\)),使得这个人到最后一个鸽子有正好 \(1\) 种方案。

数据范围:\(2\le n\le 3000\),\(0\le a_i\le n-i\)。


题解

什么时候 Codeforces 有这么 AtCoder 的题了 /yiw

为了方便,令 \(a_i=a_i+1\)(题面中条件是已经加过了的)。


有一种基于暴力的 naive 做法,可是是错的:

设 \(f_{i,k}\) 表示到第 \(i\) 个鸽子,有 \(k\) 种方案的最小宰鸽数(如果有 \(>2\) 种方案当作 \(2\))。

可是数据 1\n5\n3 1 2 1 0\n 把我宰了,因为这种做法会重复统计宰鸽。


考虑分析这个唯一的被人踩了的鸽子的序列 \(p_1,p_2,\dots ,p_m\),会发现一下性质:

  1. 对于每个 \(p_i\),这只鸽子肯定没有被宰掉,且 \(p_i+a_{pi}>p_{i+1}\)。

  2. 每个 \(p_i\) 必须满足 \(p_i+a_{pi}\le p_{i+2}\)。否则如下图最下面的红边,就会多产生一种方案。

  3. 每个 \(p_i<j<p_{i+1}\) 必须满足 \(j+a_j\le p_{i+1}\)。否则 \(p_i\) 先走橙色边,再走短的红边,就会多产生一种方案。

题解-CF1453F Even Harder


所以可以尝试维护 \(f[u][v]\) 表示最后两个 \(p_i\) 是 \(u,v\) 的方案数,然后就有了一个 \(\Theta(n^3)\) 的做法。

然后可以发现,如果给 \(u\)(从左往右第 \(2\) 个黄鸽)向右延伸的边(绿边)一个右滑的机会,那么转移可以变成 \(\Theta(n^2)\)。

即设 \(f[v][j]\) 表示当前最后一个 \(p_i=v\),然后 \(p_{i-1}\) 可以跳到 \(j\) 之前的最小宰鸽数。

\(v\) 即是图中间的黄鸽子,\(j\) 即所有绿鸽子。转移的下一个 \(v'\) 即最右端的肉鸽子。

转移过程就是枚举 \(v'\) 和 \(v\),然后从 \(f[v][v']\) 转移到 \(f[v'][v+a_v]\),代价是把 \(v\) 和 \(v'\) 之间可以跳到 \(v'\) 右边的鸽子全部宰掉。

然后把第二维前缀最小值一下,表示一个滑的过程。


代码

//George1123
#include <bits/stdc++.h>
using namespace std;

typedef long long i64;
typedef unsigned int u32;
typedef unsigned long long u64;
typedef vector<int> vi;
typedef pair<int,int> pii;

#define x first
#define y second
#define sz(a) (int)((a).size())
#define all(a) (a).begin(),(a).end()
#define R(i,n) for(int i=0;i<(n);++i)
#define L(i,n) for(int i=(n)-1;i>=0;--i)

constexpr int inf32=0x3f3f3f3f;
constexpr i64 inf64=0x3f3f3f3f3f3f3f3f;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    int t;
    for(cin>>t;t--;){
        int n;
        cin>>n;
        vi a(n);
        R(i,n) cin>>a[i],++a[i];
        vector<vi> f(n,vi(n+1,inf32));
        R(i,n)if(i) f[0][i]=0; 
        R(i,n)if(i){
            int c=0;
            L(j,i){
                if(j+a[j]<=i) continue;
                f[i][j+a[j]]=min(f[i][j+a[j]],f[j][i]+(c++));
            }
            for(int j=i+1;j<n;++j)
                f[i][j+1]=min(f[i][j+1],f[i][j]);
        }
        cout<<f[n-1][n]<<'\n';
    }
    
    return 0;
}

/*
1
5
3 1 2 1 0 
*/

/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?)
    * do smth instead of nothing and stay organized
    * WRITE STUFF DOWN
    * DON'T GET STUCK ON ONE APPROACH
*/

祝大家能踩着我这只被杀死的鸽子,越飞越远!

上一篇:328. Odd Even Linked List


下一篇:偶数卷积核大小(even-sized)与填充(padding)的副作用