本文主要是介绍AtCoder Beginner Contest 199（Sponsored by Panasonic）E - Permutation，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门
一题简单的状压dp,可能对大佬们很简单，但对现在的我来说很难。
第一眼看到题目这么多限制条件而且数据这么小，但我连暴力的方法都想不到。
用dp[S]表示在状态S下一共有多少种方案.
仔细考虑这题存在一个递推关系，当我们在选择第i个位置上放那个数时，假设我们放第k个数，
那么当前的状态只可能从：已经放了i-1个数，且没有放第k个数的状态转移而来，也就是
dp[SUk] += dp[S]，S中不包含k。且你放这个k要满足前n个数中最多只有Z个数小于等于Y。
#include<bits/stdc++.h>
using namespace std;typedef long long LL;
typedef pair<int, int> P;const int maxn = 20;
const int M_MAX = 50000 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6; int n, m;
int f[maxn][maxn];
LL dp[1 << maxn];void solve() {memset(f, INF, sizeof f); cin >> n >> m;for(int i = 0; i < m; i++) {int x, y, z;cin >> x >> y >> z;y--;f[x][y] = min(f[x][y], z);}dp[0] = 1;for(int i = 0; i < 1 << n; i++) {int cnt = __builtin_popcount(i);int sum = 0, ok = 1;for(int j = 0; j < n; j++) {if(1 << j & i) sum++;if(sum > f[cnt][j]) {ok = 0;break;}}if(ok) {for(int j = 0; j < n; j++) {if(1 << j & i) {dp[i] += dp[i^(1 << j)];}}}}cout << dp[(1<<n)-1] << endl;
}int main() {ios::sync_with_stdio(false);solve();return 0;
}
这篇关于AtCoder Beginner Contest 199（Sponsored by Panasonic）E - Permutation的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
