本文共 4036 字，大约阅读时间需要 13 分钟。

 

基准时间限制：1.5 秒 空间限制：262144 KB 分值: 640 

第一行一个整数n (1<=n<=35)。第二行是空格隔开的a[1],a[2],...,a[n]。

输出n+1行，分别为k=0,1,2,...,n时的答案。

51 5 2 4 3

11015600

题解：

首先必须要晓得利用单调栈求LIS的经典做法（不会的自己百度） 

如果没有看懂的 可以结合官方题解在进行理解：

/*51 nod 1775 LIS Counting 首先必须要晓得利用单调栈求LIS的经典做法（不会的自己百度） 而此题就是基于单调栈实现的 ，可以考虑从前往后讨论每一个字符加入还是不加人 ， 这样便可以得到母串的所有子序列，而对于所有的子序列都要求得LIS显然是不可能的，其实通过分析可以知道当前第i个字符，不管加不加入 ，之前的前i-1个字符的LIS是单调不减的 ，所以可以考虑利用之前的状态通过转移直接得到后面的状态。这很显然是个dp ，对于代码中的两个函数Choose ， Not_Choose ， 分别为当前字符加入和不加人 ， 为什么要Not_Choose ，因为用的是滚动数组 ， 所以必须将前面的所有状态进行转移由于35对于状态压缩来说还是比较大了，而LIS并不强调值本身， 值需要大小关系， 所以二进制位i+1~35并不代表i+1 ~ 35 是否在栈中， 而是表示比i大的有k个（k表示i+1 ~35 有1的位数）而Not_choose 使得sta发生变化 ， 但本质值与值之间大小关系并没有变化。如果没有看懂的 可以结合官方题解在进行理解：求LIS的经典做法是维护一个单调栈，然后从左到右扫，添加一个新元素时，找到栈中第一个比它大的元素，并用这个元素替换；如果找不到，则加到栈顶。最后栈的元素个数就是LIS长度。现在我们要DP这个东西。一个自然的想法是把这个栈的状态压成一个n位01串s。dp状态就是f[i][s]表示前i个数中取了若干，栈中的情况是s的方案数。然而n是35，直接这么搞的话状态数比较大。需要优化。观察一下转移的过程，做到第i个数时，将来会被插入的数字只有a[i+1],a[i+2],...,a[n]，因此将来的转移只和栈中数字与这些数字的大小关系有关。把a[i+1..n]的数字排序后设为b[1]
   
    <..
    
     using namespace std;#define ll long long#define N 300#define Mod 5000007ll a[N] , b[N] , f[2][Mod + 10] , st[2][Mod + 10] , tot[2] , vis[Mod + 10] , now , lst , n , Ans[N];inline void push(ll sta , ll k){	ll pos = sta % Mod;	if(vis[pos])	{		if(st[now][vis[pos]] == sta)		{			f[now][vis[pos]] += k; return ;		}		++pos;		if(pos == Mod) pos = 0;	}	vis[pos] = ++tot[now];	st[now][tot[now]] = sta;	f[now][tot[now]] = k;}inline void Not_Choose(ll x , ll sta , ll k){	ll i , num , j , pre_sta = sta , r; sta = 0;	if(x == n)	{		for(i = 1 , num = 0 ; i <= n ; ++i)		   if((pre_sta & (1ll << i))) ++num , sta |= (1ll << num);		push(sta , k);		return ;	}	for(i = 1 , num = 0 ; i < b[x + 1] ; ++i)	   if((pre_sta & (1ll << i))) ++num , sta |= (1ll << num);		for(i = x + 1; i <= n ; ++i)	    for(j = b[i] , num = b[i] , r = (i == n ? n : b[i + 1]) ; j <= r; ++j)	        if((pre_sta & (1ll << j))) ++num , sta |= (1ll << num);	push(sta , k);}inline void Choose(ll x , ll sta , ll k){	ll i;	if(sta < (1ll << a[x])) sta |= (1ll << a[x]);	else	{		sta |= (1ll << a[x]);		for(i = a[x] + 1 ; ; ++i)		{			if(((sta >> i) & 1))			{				sta ^= (1ll << i); break;			}		}	}	Not_Choose(x , sta , k);}int main(){//	freopen("test.in" , "r" , stdin);	ll i , j , k , cnt , sta;	scanf("%lld" , &n);	for(i = 1; i <= n; ++i) scanf("%lld" , &a[i]);	lst = 1 , now = 0;	push(0 , 1);	for(i = 1 ; i <= n ; ++i)	{		lst ^= 1 , now ^= 1;		memset(vis , 0 , sizeof(vis)) , tot[now] = 0;		for(j = i + 1 ; j <= n ; ++j) b[j] = a[j];		if(i != n) sort(b + i + 1 , b + n + 1);		for(j = 1 ; j <= tot[lst] ; ++j)		{			cnt = f[lst][j] , sta = st[lst][j];			Choose(i , sta , cnt);			Not_Choose(i , sta , cnt);		}	}	for(i = 1 ; i <= tot[now] ; ++i)	{		cnt = 0;		for(j = 1 ; j <= n ; ++j) if(((st[now][i] >> j) & 1)) ++cnt;		Ans[cnt] += f[now][i];	}	for(i = 0 ; i <= n ; ++i) printf("%lld\n" , Ans[i]);	return 0;}
    
   

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