1 arg (arg.cpp/in/out, 1s, 512MB)
1.1 Description
给出一个长度为 m 的序列 A, 请你求出有多少种 1...n 的排列, 满足 A 是它的一个 LIS.
1.2 Input Format
第一行两个整数 n,m.
接下来一行 m 个整数, 表示 A.
1.3 Output Format
一行一个整数表示答案.
1.4 Sample
1.4.1 Input
5 3
1 3 4
1.4.2 Output
11
1.5 Constraints
对于前 30% 的数据, n ≤ 9;
对于前 60% 的数据, n ≤ 12;
对于 100% 的数据, 1 ≤ m ≤ n ≤ 15.
分析：挺难的一道题.
next_permutation+暴力判断可以骗得30分. 阶乘复杂度是肯定不行的，指数复杂度才可以.
那么状压dp？可以参考hdu4352的状压方法. 那还有一维表示什么呢？ 我一开始想的是表示前i个数，这样推出来的答案显然是不对的.于是我又想着表示插入了1~i这些数. 错的更离谱了......为什么一定要按顺序插入呢？
正确的状态表示方法应该是f[s][S]，s表示所有数的状态（选中or没选中），S表示lis的状态.每次从s中选择一个没有被选中的数转移即可.这样就保证了选的数不会重复.
但是这样复杂度太高了. 而且数组开不下.尝试去优化它. 一个比较明显的结论：S一定是s的子集. 出现在lis中的数在原数列中一定已经出现了.所以可以将状态压成3进制. 第i位为0表示这个数既没有出现在原数列中，也没有出现在lis中,1表示都出现了,2表示没有出现在lis中.这样的话数组就能开下了,时间复杂度O(3^n * n),可以过.
还有一个关键的问题：如何保证A是排列的lis呢？ 两个约束条件:
1.ai出现的位置一定在ai+1出现的位置之前.
2.lis的长度正好＝m.
对于第一个约束条件，在转移的时候判断一下上一位是否已经出现在lis中即可.
对于第二个约束条件，如果转移后得到的新状态的lis长度>m，则不转移. 因为保证状态中所有的ai都转移到了，当所有的数在排列中都出现时，累加答案即可.
挺好的一道题.没想到状态的正确表示是因为我觉得复杂度太高了，数组也开不下. 有时候想dp题是不能一步到位的.先想一个常规的表示方法，再来优化它是一种很好的分析方法.
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; int n,m,a[20],id[20]; ll f[14348907],jie[20],ans,zhuangtai[20]; int main() { scanf("%d%d",&n,&m); for (int i = 1; i <= m; i++) { scanf("%d",&a[i]); id[a[i]] = i; } f[0] = 1; jie[0] = 1; for (int i = 1; i <= 15; i++) jie[i] = jie[i - 1] * 3; for (int sta = 0;sta < jie[n];sta++) { if(!f[sta]) continue; int t = sta; int num = 0,cnt = 0; for (int i = 1; i <= n; i++) { zhuangtai[i] = t % 3; t /= 3; if (zhuangtai[i]) num++; if (zhuangtai[i] == 1) cnt++; } if (num == n) { ans += f[sta]; continue; } for (int i = 1; i <= n; i++) { if (zhuangtai[i]) continue; if (id[i] > 1 && !zhuangtai[a[id[i] - 1]]) continue; int tot = 0; for (int j = 1; j < i; j++) { if (!zhuangtai[j]) continue; if (zhuangtai[j] == 1) tot++; } if (tot == cnt) { if (tot == m) continue; int nsta = sta + jie[i - 1]; f[nsta] += f[sta]; continue; } int nsta = sta + jie[i - 1]; for (int j = i + 1; j <= n; j++) { if (zhuangtai[j] == 1) { nsta += jie[j - 1]; break; } } f[nsta] += f[sta]; } } cout << ans << endl; return 0; }