T551863 拒绝高低房

BigRooster · 2024-12-17 18:51:33 · 题解

注意到，如果第 i 间房子可以与第 j 间房子在同一分组中（j<i），那么一定要满足一个条件：设 l_i 表示第 i 间房左边第一个和它差大于 k 的房子，则 j>l_i。那么状态转移方程就出来了：dp_i=\sum\limits^{i-1}_{j=l_i}dp_j。

提交后可以得到0分的好成绩。

为什么呢？

考虑 [1,4,2],k=2 这个序列：l_2=0，但 [1,4,2] 显然不能放在同一组，因为 1,4 不满足要求，因此可以发现，如果前一个数的 l 小于当前数，那么当前数也不能到达 l_{i-1} 左边。故应加上预处理 l_i=min\{l_i,l_{i-1}\}。

然后写出代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k;
int a[200001];
int dp[200010];
int lmao[200001];
const int mod=1000000007;
int aaabs(int x,int y)
{
    return max(x,y)-min(x,y);
}
main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
//  ifstream cin("8.in",ios::in);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        for(int j=i-1;j;j--)
            if(aaabs(a[j],a[i])>k)
            {
                lmao[i]=j;
                break;
            }
        lmao[i]=max(lmao[i],lmao[i-1]);
//      cout<<lmao[i]<<" ";
    }
//  cout<<endl;
    dp[1]=dp[2]=1;
    for(int i=2;i<=n;i++)
    {
//      dp[i+1]=dp[i]-dp[lmao[i]];
//      dp[i+1]=(dp[i]+dp[i+1])%mod;
        int sum=0;
        for(int j=lmao[i]+1;j<=i;j++)
            sum+=dp[j];
        dp[i+1]=sum,dp[i+1]=(dp[i+1]+mod)%mod;
    }
    cout<<dp[n+1]%mod;
}

注意到中间dp可以用前缀和优化，因此，边dp边将现在的dp值加上之前的形成前缀和，前面的 l_i 预处理可以用单调栈优化，时间复杂度 O(n)。

代码还没写。