题解：SP6950 CTOI10D3 - A HUGE TOWER

· · 题解

简要题意

给你个序列，让你求用这个序列构造一个序列使它满足 h_i - h_{i -1} \le D 的方案个数

思路

首先，我们读完题后大概就能想到做法了。

我们可以采用插板的思想，先把原序列排个序，因为我们是重构所以顺序无所谓了，我们接下来可以转换一下，求出一个值域来，看能选多少个数，然后我们把这些数字放到插进去，看能插多少个方案，最后我们用乘法原理求一下就可以。

这个题其实也就是 DP，所以我们也可以设计一个转移，设 f_i 表示前 i 个数能构造的方案数。

转移：f_i = f_{i-1} \times (i - l + 1)

边界条件：$f_0=1

原因：首先乘法原理，是因为上一位的选择与当前这一位的方案数是互相干扰的所以是 f_{i-1} \times (i-l+1)。然后边界什么都不选也是一种方案，而且为了我们的计算方便，也直接把边界设到 f_1 但是没有必要。

实现：写一个双指针，求最大下标 l，然后 DP 不用再额外定义一个数组直接计算即可。

AC code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 6.2e5 + 10;
const ll mod = 1e9 + 9;
int n,D;
ll ans = 1,h[N];//输出爆零的元凶！！！
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n>>D;
    for(int i = 1;i <= n;++i)cin>>h[i];
    sort(h + 1,h + 1 + n);
    int l = 1;
    for(int i = 1;i <= n;++i){
        while(l < i&&h[i] - h[l] > D)l++;
        ans = ans * (i - l + 1) % mod;
    }
    cout<<ans<<'\n';
}

二倍经验:P6522 [CEOI 2010] tower (day2)