首页 > 代码库 > UVALive 7143 Room Assignment（组合数学+DP）
UVALive 7143 Room Assignment（组合数学+DP）
题目链接
参考自：http://www.cnblogs.com/oyking/p/4508260.html
题意
n个人，其中有k对双胞胎.现有m间房间，每间房间有容量ci问分配房间的方案数。
分析
设dp[i][j]为已经放满了第i个房间之后，所剩下的双胞胎的对数还有j对，然后对于i+1间房，我们可以从剩余的j对中选择出a对，每对双胞胎只是放一个就好，然后又从j-a对双胞胎中选b对全部放进去，然后再从剩余的sum-j2中选择c[i]-a-2b个放进i+1个房间里面,这样的话就能得到转移方程，dp[i+1][j-a-b]=dp[i][j]C(j,a)C(j-a,b)C(sum-j2,c[i]-a-b2);然后组合数就用逆元去算就ok了。时间复杂度是O（（mk）³）
#include <cstdio>#include <algorithm>#include <iostream>#include <cstring>using namespace std;typedef long long LL;const int MAXN = 100010;const int MOD = 1e9 + 7;int inv[MAXN], fact[MAXN];int _inv(int x) { if(x == 1) return 1; return LL(MOD - MOD / x) * _inv(MOD % x) % MOD;}void init(int n = 100000) { fact[0] = 1; for(int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * LL(i) % MOD; for(int i = 0; i <= n; ++i) inv[i] = _inv(fact[i]);}LL comb(int a, int b) { if(a < b) return 0; return LL(fact[a]) * inv[b] % MOD * LL(inv[a - b]) % MOD;}int dp[13][111];int c[13];int T, n, m, k;int mulmul(LL a, LL b, LL c, LL d) { return a * b % MOD * c % MOD * d % MOD;}void update_add(int &a, int b) { a += b; if(a >= MOD) a -= MOD;}int solve() { memset(dp, 0, sizeof(dp)); dp[0][k] = 1; for(int i = 0, sum = n; i < m; ++i) { for(int r = 0; r <= k; ++r) if(dp[i][r]) { if(sum < 2 * r) break; for(int a = 0; a <= r; ++a) { for(int b = 0; b + a <= r; ++b) { if(c[i + 1] - a - 2 * b < 0) break; int t = mulmul(dp[i][r], comb(r, a), comb(r - a, b), comb(sum - 2 * r, c[i + 1] - a - 2 * b)); update_add(dp[i + 1][r - a - b], t); } if(i == m - 1) break; /// if i = m - 1 then a must be zero } } sum -= c[i + 1]; } return dp[m][0];}int main() { init(); //printf("%d\n", comb(10, 1)); scanf("%d", &T); for(int t = 1; t <= T; ++t) { scanf("%d%d%d", &n, &m, &k); for(int i = 1; i <= m; ++i) scanf("%d", &c[i]); printf("Case #%d: %d\n", t, solve()); }}
UVALive 7143 Room Assignment（组合数学+DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。