题目

~~据说是 ATCODER 的题。~~

题目描述

沐目女未喜欢进步。她的名言：“又来了两个人，我又要

{\tt rnk}\;-=2

了！”

今天她又要进步。她要瞎选一些元素，但是要保证构成的子序列单调上升。~~什么糟糕要求啊喂。~~

具体来说，对于所有可加入的元素，她会等概率的选择一个并加入。“可加入” 指，加入这个元素之后，子序列仍然是单增的。如果没有可加入的元素，她就会眼泪汪汪的结束选择。

你能告诉可爱的沐目女未最终选出的元素的期望数量吗？

数据范围与提示

n\le 2\times 10^3

且

a_i\le n

且

a_i\ne a_j(i\ne j)

。

思路

区间 $\tt dp$ 的思路比较显然。

用 $f (l, r)$ 表示 $(l, r)$ 之间继续选择，已经选择了 $a_l$ 和 $a_r$ 。那么有转移方程

$f(l,r)=1+\sum_{l<k<r}^{a_l<a_k<a_r}\frac{f(l,k)+f(k,r)}{|S|}$

想个办法优化。这里就要给区间 $\tt dp$ 只会枚举长度与左端点的人（包括我自己）提个醒了：区间 $\tt dp$ 还有一种枚举方式是 左端点从大到小、右端点从小到大。

如果是这种枚举方式，可以用树状数组优化。因为就是求 $a_l<a_k<a_r$ 的 $k$ 的所有 $f (l, k)$ 的和。至于 $f (k, r)$ ，可以对于每个 $r$ 都开一个树状数组 😉

于是 $\mathcal O(n^2\log n)$ 解决了。~~话说不会被卡常咩。~~

代码

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;typedef long long int_;inline int readint(){   	int a = 0; char c = getchar(), f = 1;	for(; c<'0'||c>'9'; c=getchar())		if(c == '-') f = -f;	for(; '0'<=c&&c<='9'; c=getchar())		a = (a<<3)+(a<<1)+(c^48);	return a*f;}template < typename T >inline void getMax(T &a,const T &b){   	(a < b) ? (a = b) : 0;}template < typename T >inline void getMin(T &a,const T &b){   	(b < a) ? (a = b) : 0;}const int MaxN = 2010;const int Mod = 1e9+7;int a[MaxN], dp[MaxN][MaxN], n;struct BIT{   	int c[MaxN];	void clear(){   		for(int i=1; i<=n; ++i)			c[i] = 0;	}	void modify(int id,int v){   		for(int i=id; i<=n; i+=(i&-i))			c[i] = (c[i]+v)%Mod;	}	int query(int id){   		if(id > n) id = n;		int res = 0;		for(int i=id; i; i-=(i&-i))			res = (res+c[i])%Mod;		return res;	}};BIT r[MaxN]; // 每个右端点都开一个BIT cnt, l; // cnt是个数 l是当前左端点int_ inv[MaxN]; // 逆元int main(){   	n = readint();	for(int i=1; i<=n; ++i)		a[i] = readint();	inv[1] = 1; // 预处理逆元	for(int i=2; i<=n; ++i)		inv[i] = (Mod-Mod/i)			* inv[Mod%i]%Mod;	a[n+1] = n+1; // 末尾的虚点	for(int i=n-1; i>=0; --i){   		l.clear(), cnt.clear();		for(int j=i+2; j<=n+1; ++j){   			r[j].modify(a[i+1],dp[i+1][j]);			l.modify(a[j-1],dp[i][j-1]);			cnt.modify(a[j-1],1);			int s = cnt.query(a[j])				- cnt.query(a[i]);			if(s <= 0) continue;			int all = l.query(a[j])				- l.query(a[i])				+ r[j].query(a[j])				- r[j].query(a[i]);			all = (all%Mod+Mod)%Mod;			dp[i][j] = (all*inv[s]+1)%Mod;// printf("dp[%d,%d] = %d\n",i,j,dp[i][j]);		}	}	printf("%d\n",dp[0][n+1]);	return 0;}

转载地址：http://lntq.baihongyu.com/

你可能感兴趣的文章