T551863 拒绝高低房

注意到，如果第

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}\}

。

然后写出代码：

CPP

#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)

。

代码还没写。

T551863 拒绝高低房

文章操作

相关推荐

评论

T551863 拒绝高低房