原来的序列是n的排列，给出原来的序列的的一组最长不下降子序列，求原序列可以多少种。 (1<=n<=15)
状态压缩dp加暴力枚举状态。 求最长不下降子序列一种log算法就是开一个辅助数组l， lx 表示长度为x的序列的结尾最小是多少。 l是单调递增的。 设 fi,S 表示已经放了i个，状态是S的方案数。 一个数如果已经放了，并且在l里出现了，是2，放了，没在l中出现是1，没放是0. 因为l是单调递增的，所以我们可以由状态还原l数组。 于是我们可以一层一层地暴力，就算加上了一点剪枝，这样状态数有点大。 状态数剪枝1：当前最长不下降子序列的长度不能超过输入的长度。 状态数剪枝2：假设要加的数字是x，如果有一输入的数a[i]，它没有在当前中出现过，且a[i]>x,f[x]>=i,那么这个状态一定不合法。
Code：
#include<cstdio> #include<algorithm> #define ll long long #define fo(i, x, y) for(int i = x; i <= y; i ++) #define min(a, b) ((a) < (b) ? (a) : (b)) using namespace std; int n, m, ans, a[20], l[20], d[20], bz[20]; void insert(int x) { int p = 0; for(int q = 1, r = l[0]; q <= r; ) { int m = (q + r) / 2; if(l[m] < x) p = m, q = m + 1; else r = m - 1; } if(p == l[0]) l[++ l[0]] = x; else l[p + 1] = min(l[p+ 1], x); } void dg(int x, int r) { if(l[0] > m) return; if(x > n) { ans ++; return; } int l1[20]; fo(i, 0, l[0]) l1[i] = l[i]; if(r <= m) insert(a[r]), dg(x + 1, r + 1); fo(i, 0, l1[0]) l[i] = l1[i]; fo(i, 1, d[0]) { insert(d[i]); swap(d[i], d[d[0]]); d[0] --; dg(x + 1, r); d[0] ++; swap(d[i], d[d[0]]); fo(j, 0, l1[0]) l[j] = l1[j]; } } int main() { scanf("%d", &n); scanf("%d", &m); fo(i, 1, m) scanf("%d", &a[i]), bz[a[i]] = 1; fo(i, 1, n) if(!bz[i]) d[++ d[0]] = i; dg(1, 1); printf("%d", ans); }