JZOJ 3712【NOI2014模拟6.30】石中剑的考验

题目大意：

原来的序列是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);
}