P3970 [TJOI2014] 上升子序列题解

题意

给定一个整数序列，求它的上升子序列个数，且这些上升子序列的长度至少为2。

思路

我们可以先简化一下问题，将只有1个元素的子序列也算入内（后文第一个式子中的+1），最后将它们从答案中减去（后文第二个式子中的-1）。

考虑DP，设 dp[a[i]] 为以 a[i] 结尾的子序列个数，可得到状态转移方程为：

dp_{a_{i}}= \left ( \sum_{j=1}^{i-1} \left [ a_{j}< a_{i} \right ]\times dp_{a_{j}} \right )+1

最终答案为：

ans= \sum_{i=2}^{qaq}\left ( dp_{i}-1 \right )

代码实现为：

CPP

for(int i=1;i<=n;i++){
	for(int j=1;j<i;j++)
		if(a[j]<a[i])dp[a[i]]=(dp[a[i]]+dp[a[j]])%mod;
	dp[a[i]]=(dp[a[i]]+1)%mod;
}
for(int i=2;i<=qaq;i++)
	ans=(ans+dp[i]-1)%mod;
//qaq为离散化后的a的最大值

但这样的时间复杂度为 O(n^2) ，只能得到30分。

考虑优化：

不难发现，这个转移方程可以用树状数组或线段树进行维护，将转移的时间复杂度由 O(n) 降低到 O(logn)，总时间复杂度降低为 O(nlogn)，能通过100%的数据点。

在这里使用代码更简短的树状数组，核心代码如下：

CPP

for(int i=1;i<=n;i++){
	int tmp=query(a[i]-1);
	update(a[i],tmp+1-dp[a[i]]);
	dp[a[i]]=(tmp+1)%mod;
}

完整代码

30tps代码：

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5,mod=1e9+7;
int n,a[N],rk[N];ll dp[N],ans;
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i],rk[i]=a[i];
	sort(rk+1,rk+n+1);
	int qaq=unique(rk+1,rk+n+1)-(rk+1);
	for(int i=1;i<=n;i++)
		a[i]=lower_bound(rk+1,rk+qaq+1,a[i])-rk;
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++)
			if(a[j]<a[i])dp[a[i]]=(dp[a[i]]+dp[a[j]])%mod;
		dp[a[i]]=(dp[a[i]]+1)%mod;
	}
	for(int i=2;i<=qaq;i++)
		ans=(ans+dp[i]-1)%mod;
	cout<<ans;
	return 0;
}

AC代码

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(x) (x&-x)
const int N=1e5+5,mod=1e9+7;
int n,a[N],rk[N];ll tr[N],dp[N],ans;
void update(int x,int v){
	while(x<=n)
		tr[x]=(tr[x]+v)%mod,x+=lowbit(x);
}
ll query(int x,ll ans=0){
	while(x)
		ans=(ans+tr[x])%mod,x-=lowbit(x);
	return ans;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i],rk[i]=a[i];
	sort(rk+1,rk+n+1);
	int qaq=unique(rk+1,rk+n+1)-(rk+1);
	for(int i=1;i<=n;i++)
		a[i]=lower_bound(rk+1,rk+qaq+1,a[i])-rk;
	for(int i=1;i<=n;i++){
		int tmp=query(a[i]-1);
		update(a[i],tmp+1-dp[a[i]]);
		dp[a[i]]=(tmp+1)%mod;
	}
	for(int i=2;i<=qaq;i++)
		ans=(ans+dp[i]-1)%mod;
	cout<<ans;
	return 0;
}

30tps记录 AC记录

P3970 [TJOI2014] 上升子序列题解

文章操作

题意

思路

完整代码

相关推荐

评论

P3970 [TJOI2014] 上升子序列题解