• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

洛谷 P3970 [TJOI2014]上升子序列 题解

开发技术 开发技术 4小时前 2次浏览

之前莫名其妙一直 (80) 分,今天突然看到这题,就顺手把它过了。

首先不考虑去重和长度大于 (1),上升子序列个数还是很好求的,大概是 DP 设 (dp_i) 表示以 (a_i) 结尾的上升子序列个数。转移方程大致如下:

[dp_i=1+sum_{j=1}^{i-1}dp_j[a_j<a_i]
]

容易用树状数组或线段树优化(O(nlog n))。接下来主要去重的问题。

容易发现的是,如果存在 (i,j(i<j)) 满足 (a_i=a_j),那么对于后面一个点 (k(j<k)) 的贡献应当只计算 (j) 提供的而不计算 (i) 的。所以在计算完 (j)(dp_j) 后,在树状数组中要把 (dp_i) 给减掉。这样就不会算重了。

我们可以预处理出每一个 (a_j) 前面第一个和它相等的位置 (a_j)。这样就可以树状数组了。

最后在减去长度为 (1) 的情况。注意要离散化。

代码比较奇怪(离散化用的 map),请理性参考。

// By: Little09
// Problem: P3970 [TJOI2014]上升子序列
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3970
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n;
const ll mod=1000000007;
const int N=500005;
ll tree[N];
ll a[N],b[N],dp[N];
int used[N],pre[N];
int cnt;
map<int,int>q;
inline int lowbit(int x)
{
	return x&(-x);
}
inline void add(int x,ll k)
{
	for (;x<=n;x+=lowbit(x)) tree[x]=(k+tree[x])%mod;
}
inline ll ask(int x)
{
	ll ans=0;
	for (;x;x-=lowbit(x)) ans=(tree[x]+ans)%mod;
	return ans;
}
inline int read()
{
    int F=1,ANS=0;
	char C=getchar();
    while (C<'0'||C>'9')
	{
		if (C=='-') F=-1;
		C=getchar();
	}
    while (C>='0'&&C<='9')
	{
		ANS=ANS*10+C-'0';
		C=getchar();
	}
    return F*ANS;
}
int main()
{
	n=read();
	for (int i=1;i<=n;i++) b[i]=a[i]=read();
	sort(b+1,b+n+1);
	for (int i=1;i<=n;i++)
	{
		if (i==1||b[i]!=b[i-1]) q[b[i]]=++cnt;
	}
	for (int i=1;i<=n;i++) 
	{
		int u=q[a[i]];
		pre[i]=used[u];
		a[i]=u;
		used[u]=i;
	}
	dp[1]=1;
	add(a[1],1);
	for (int i=2;i<=n;i++)
	{
		if (pre[i]==0) 
		{
			dp[i]=(ask(a[i]-1)+1)%mod;
			add(a[i],dp[i]);
		}
		else 
		{
			dp[i]=(ask(a[i]-1)+1)%mod;
			add(a[i],dp[i]-dp[pre[i]]);
		}
	}
	ll ans=ask(n);
	for (int i=1;i<=n;i++) ans=(ans-(pre[i]==0));
	cout << ans;
	return 0;
}

程序员灯塔
转载请注明原文链接:洛谷 P3970 [TJOI2014]上升子序列 题解
喜欢 (0)