题目链接
题目大意
给定 (M) 个约束条件，问满足这 (M) 个约束条件的长度为 (N) 排列有多少个
每个约束条件为一个三元组 ((x , y, z))，要求 (a_1,a_2,..,a_x) 小于 (y) 的数的个数不超过 (z)
解题思路
可以将 (x) 位置的约束条件存储在 (vec[x]) 中
于是定义 (dp[i][bit]) 表示：
- 用 (bit) 这个状态对应的数（这些数都得用上）
- 组成长度为 (i) 的排列的方案数
- （这些排列需要满足 (vec[1]) ~ (vec[i]) 的约束条件）
那么答案就为 (dp[n][(1 << n) - 1])
- 而如果 (bit) 这个状态对应的数的个数等于 (i)
- 且这 (i) 个数满足 (vec[i]) 的约束条件
那么可得：
for(int k = 0 ; k < n ; k ++) { if(bit >> k & 1) dp[i][bit] += dp[i - 1][bit - (1 << k)]; }然后考虑一波优化。
先定义 (cnt(bit)) 表示 (bit) 这个状态对应的数的个数。
上面有个 (dp) 的转移条件是 ：
- (bit) 这个状态对应的数的个数等于 (i)，
也就是说只有当 (i = cnt[bit]) 时才能进行转移（只有 (dp[cnt(bit)][bit]) 是有效的）
那么只要枚举 (bit)，就可以得到对应有效的 (i) ((i = cnt(bit)))
于是我们可以去掉 (dp) 数组的一维，并去掉一层循环
即定义 (dp[bit]) 表示：
- 用 (bit) 这个状态对应的数（这些数都得用上）
- 组成长度为 (cnt[bit(i)]) 的排列的方案数
- （这些排列需要满足 (vec[1]) ~ (vec[cnt(bit)]) 的约束条件）
最后答案为 (dp[(1 << n) - 1])，转移方程类似
AC_Code
#include<bits/stdc++.h>
using namespace std;
int get(int x)
{
int res = 0;
while(x)
{
if(x & 1) res ++ ;
x >>= 1;
}
return res;
}
vector<pair<int , int>>vec[19];
long long dp[1 << 18];
int cnt[1 << 18];
signed main()
{
int n , m , x , y , z;
cin >> n >> m;
for(int i = 1 ; i <= m ; i ++)
{
cin >> x >> y >> z;
vec[x].push_back(make_pair(y , z));
}
for(int bit = 1 ; bit < (1 << n) ; bit ++) cnt[bit] = get(bit);
dp[0] = 1;
for(int bit = 0 ; bit < (1 << n) ; bit ++)
{
vector<int>num;
for(int k = 0 ; k < n ; k ++)
{
if(bit >> k & 1) num.push_back(k + 1);
}
int flag = 0;
for(auto q : vec[cnt[bit]])
{
int y = q.first , z = q.second , sum = 0;
for(auto h : num)
{
if(h <= y) sum ++ ;
}
if(sum > z) { flag = 1 ; break ; }
}
if(flag) continue ;
for(auto k : num) dp[bit] += dp[bit - (1 << (k - 1))];
}
cout << dp[(1 << n) - 1] << '
';
return 0;
}