专栏文章

P10592题解

SStuart220_Chen
P10592题解参与者 8已保存评论 13

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
13 条
当前快照
1 份
快照标识符
@miqj090m
此快照首次捕获于
2025/12/04 05:35
3 个月前
此快照最后确认于
2025/12/04 05:35
3 个月前
查看原文
看见各位大神都是直接给的思路，本蒟蒻就奉上自己的解题过程吧。

第一步：暴力 dfs

看了看题，发现题意是若序列不是不下降子序列，则从中删除一个数，问一共有多少种删法，哎呀，没思路，算了，先打 dfs 找找规律吧。于是就有了如下代码。
CPP
//朴素的暴力
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[2010],vis[2010];
int ans,n,mod=1e9+7;
void dfs(int u)
{
	int last=-1,flag=1;
	for(int i=1;i<=n;i++)
	{
		if(vis[i]==0)
		{
			if(a[i]<last) flag=0;//如果剩下的数不是不下降子序列，则flag=0。
			last=a[i];
		}
	}
	if(flag==1)
	{
		ans=(ans+1)%mod;//如果是不下降子序列的话，统计答案
		return;
	}
	for(int i=1;i<=n;i++)//枚举删哪些数
	{
		if(vis[i]==0)
		{
			vis[i]=1;//删掉他的话标记为1
			dfs(u+1);
			vis[i]=0;//回溯
		}
	}
}
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];//输入
	dfs(1);
	cout<<ans;
	return 0;
}

第二步：暴力 dp

不难发现这道题应该和数学有关， dpi,jdp_{i,j} 表示以 i 为结尾，长度为 j 的不下降子序列。转移方程为：

dpi,j=∑k=1k<i且ak≤aidpk,j−1dp_{i,j}=\sum_{k=1}^{k<i且a_k\le a_i}dp_{k,j-1}。

那么 ans 又该如何统计呢。先默认所有的数都只能删到只剩这一个数，所以 ans 赋初始值为 n×An−1n−1n\times A_{n-1}^{n-1}（剩下 n−1n-1 个数有 An−1n−1A_{n-1}^{n-1} 种删法）然后一边计算 dpi,jdp_{i,j} 一边统计ans，ans每次减少：

dpi,j×(len−1)×An−lenn−lendp_{i,j}\times (len-1)\times A_{n-len}^{n-len}

（表示每一种以 i 结尾长度为 j 的不下降子序列里的每一个长度为 (n−1)(n-1) 的不下降子序列都会因为这个子序列而惨遭减去 An−lenn−lenA_{n-len}^{n-len} 种情况，就像我的零花钱一样，但是因为留下这个序列也算一种方法，所以还要再加上 An−lenn−lenA_{n-len}^{n-len} 种，总结下来就是如上公式），累死我了，下奉上代码。
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long//好用，多用
int a[2010],dp[2010][2010];
int ans,n,mod=1e9+7,cnt;
int ff(int x)
{
	int ret=1;
	for(int i=1;i<=x;i++) ret=(ret*i)%mod;
	return ret;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);//关同步流
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		dp[i][1]=1;
	}
    ans=(n*ff(n-1))%mod;//初始化
	for(int i=1;i<=n;i++)
	{
		for(int len=2;len<=i;len++)
		{
			for(int j=1;j<i;j++)
			{
				if(a[j]<=a[i])
				{
					dp[i][len]+=dp[j][len-1];//dp转移方程
				}
			}
			ans=(ans-(dp[i][len]*(len-1)%mod)*ff(n-len)+mod*mod)%mod;//如上公式
		}
	}
	cout<<ans;
	return 0;
}
复杂度 O(n3)O(n^3)。

第三步：树状数组优化dp

很明显上面的代码还有优化的空间，aj≤aia_j\le a_i 这一步可以使用树状数组优化，只需要让树状数组以 aia_i 为下标，然后每次调用 query(a[i])。这里还有一个问题，len 这一维要倒序循环，并且调用 query 和 add 函数时只用遍历 i 这一维，大家可以自行思考一下这是为什么。下面上代码。
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[2010],lsh[2010],dp[2010][2010],k[2010],sum[2010][2010];
int ans,n,mod=1e9+7,cnt,maxx;
int ff(int x)
{
	int ret=1;
	for(int i=1;i<=x;i++) ret=(ret*i)%mod;
	return ret;
}
int lowbit(int x)
{
	return x&(-x);
}
void add(int x,int y,int k)
{
	for(int i=x;i<=n;i+=lowbit(i))
	{
		sum[i][y]=(k+sum[i][y])%mod;
	}
}
int query(int x,int y)
{
	int ret=0;
	for(int i=x;i;i-=lowbit(i))
	{
		ret=(ret+sum[i][y])%mod;
	}
	return ret;
}
signed main()
{
	cin>>n;
	int flag=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		lsh[i]=a[i];
		if(a[i]<a[i-1] && i!=1) flag=1;
	}
	if(flag==0)
	{
		cout<<1;
		return 0;
	}
	sort(lsh+1,lsh+n+1);
	int cnt=unique(lsh+1,lsh+1+n)-lsh-1;
	for(int i=1;i<=n;i++)
	{
		a[i]=lower_bound(lsh+1,lsh+1+cnt,a[i])-lsh;
		maxx=max(maxx,a[i]);
	}
	for(int i=1;i<=n;i++) k[i]=ff(i);
	for(int i=1;i<=n;i++)
	{
		ans=(ans+ff(n-1))%mod;
		for(int len=i;len>=2;len--)
		{
			int tot=query(a[i],len-1);
			add(a[i],len,tot);
			if(tot>0)
			{
				ans=(ans-(tot*(len-1)%mod)*k[n-len]%mod+mod*mod)%mod;
			}
		}
		add(a[i],1,1);
	}
	cout<<ans;
	return 0;
}
时间复杂度 O(n2∗log2n)O(n^2*log_2n)，完美AC。

评论

共 13 条评论，欢迎与作者交流。

正在加载评论...