P15301 [ROI 2012 Day 2] army 汗国军队

思路

首先直接做是不太好做的，因为要同时满足两个限制：

  • 最长的 LIS 长度为 $k$；
  • 给定的长度为 $k$ 的 $g$ 数组必须在序列里按顺序排列。

考虑拆分这两个问题。
首先忽略第二部分，考虑第一部分。
我们发现，从大到小地在数组任意位置插入所有数就可以构成所有排列。
那模拟这个插入的过程。
容易发现 LIS 数组的每个位置相比上一个位置最多增加 $1$，这是显然的，不然你每次都只加了一个数还能多更多不成。
那就考虑对整个 LIS 数组进行一个差分，这样每一位都是 $1$ 或是 $0$，整个数组可以用状压表示。
因为此时插入的数比已有的其它数都要大，所以它后面的数无法接在它自己后面使得 LIS 变长，而它一定可以接在它前面的任意数后面使得 LIS 变长 $1$。
插入的过程就相当于在插入的位置加上一个 $1$，然后删掉后面最近的一个 $1$（在本位多一，后面自然就要少一，但是原本的 $0$ 可以继承本位，所以不变），这一步可以通过位运算轻易地得出。
考虑一个 $f_{i,j}$，$i$ 表示要插入的数，$j$ 表示插入前的状态，再枚举一个插入的位置 $t$，那右边部分 $r$ 即为j>>(t-1)，左边部分 $l$ 就是j-(r<<t)。
因为要删掉后面的第一个 $1$，所以r-=lowbit(r)。
然后要插入一个 $1$，所以l+=(1<<(t-1))。
那第一部分的内层 DP 就做完了。
要做第二部分也是简单的，只需加一维状态，表示插入到了 $g$ 数组的哪一个值。
然后因为是递增填的，所以所有护卫一定能构成一个长度为 $k$ 的 IS，LIS 的长度即为前面差分数组里 $1$ 的数量，若等于 $k$ 则成立。

代码

正解比暴力短说是。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
#define fir first
#define sec second 
#define int long long
#define pii pair<int,int>
#define fep(i,s,e) for(int i=s;i<e;i++)
#define pef(i,s,e) for(int i=s;i>e;i--)
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define per(i,s,e) for(int i=s;i>=e;i--)
namespace FastIO{
	template<typename T>inline void read(T &x){
		x=0;int f=1;char c=getchar();
		for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
		for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);x*=f;
	}
	template<typename T,typename...Args>
    inline void read(T &x,Args&...args){
        read(x);
        read(args...);
    }
	template<typename T>void print(T x){
		if(x<0)x=-x,putchar('-');
		if(x>9)print(x/10);
		putchar((x%10)^48);
	}
}
using namespace std;
using namespace FastIO;
const int N=16;
int n,m,g[N],G[N];
int f[N][1<<N][N];
int lowbit(int x){
	return x&-x;
}
signed main(){
	read(n,m);
	rep(i,1,m)read(g[i]),G[g[i]]=1;
	f[0][0][0]=1;
	rep(i,1,n){
		fep(j,0,(1<<(i-1))){
			fep(k,0,i){
				int st=1;
				if(G[i])st=k+1;
				rep(t,st,i){
					int r=(j>>(t-1));
					int l=j-(r<<(t-1));
					r-=lowbit(r);
					l+=(1<<(t-1));
					int nxt=k+(t<=k);
					if(G[i])nxt=t;
					f[i][l+(r<<t)][nxt]+=f[i-1][j][k];
				}
			}
		}
	}
	int ans=0;
	fep(i,0,(1<<n)){
		if(__builtin_popcount(i)==m){
			rep(j,0,n)ans+=f[n][i][j]; 
		}
	}
	print(ans);
}