首页 > 代码库 > ZOJ-3777-Problem Arrangement(状态DP)
ZOJ-3777-Problem Arrangement(状态DP)
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3777
题意:
输入n和m,接下来一个n*n的矩阵,a[i][j]表示第i道题放在第j个顺序做可以加a[i][j]的分数,问做完n道题所得分数大于等于m的概率。用分数表示,分母为上述满足题意的方案数,分子是总的方案数,输出最简形式。
分析:
一开始用的DFS做的,复杂度太高,果断超时。。
正解是状压DP:
由于总的方案数为n! ,简化为求给一个n*n的矩阵,每一行每一列各选一个数使得n个数之和大于等于m的方案数。
n的范围是1 <= n <= 12,每一列选与不选分别用1和0表示,状态数最多达到1<<12。
dp[sta][score]表示状态为i得分为j的方案数。
sta通过二进制上1的位置来表示哪几列被选了。
在当前状态下,对于某一列j,若sta&(1<<j) == 0说明第j列还未选,继而可以由第j列来更新,否则说明第j列已经被选。
状态转移方程为:
其中i当前状态的可行的上一状态,cnt为当前sta选到了第几行。
由于从当前状态寻找上一状态很困难,所以我们反着来,用上一状态更新它可达的下一状态(具体看代码)
最后dp[ (1<<n) -1 ][ m ]表示每行每列各取一个数,最后取n个数并得分大于等于m的方案数。(将动态转移方程变化了一下)
说的不是很明白,代码写的很清楚。
代码:
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; int dp[1<<12][510]; int f[13]; int a[13][13]; int gcd(int a, int b) { if(b == 0) return a; return gcd(b,a%b); } int main() { int test; int n,m; f[0] = 1; for(int i = 1; i <= 12; i++) f[i] = f[i-1] * i; scanf("%d",&test); while(test--) { scanf("%d %d",&n,&m); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) scanf("%d",&a[i][j]); for(int i = 0; i < (1<<n); i++) for(int j = 0; j <= m; j++) dp[i][j] = 0; dp[0][0] = 1; for(int i = 0; i < (1<<n); i++) { int cnt = 0; for(int j = 1; j <= n; j++) { if(i & (1<<(j-1)) ) cnt++; } for(int j = 1; j <= n; j++) { if(i & (1<<(j-1))) continue; for(int g = 0; g <= m; g++) { if(g + a[cnt+1][j] >= m) dp[i+(1<<(j-1))][m] += dp[i][g]; else dp[i+(1<<(j-1))][g+a[cnt+1][j]] += dp[i][g]; } } } if(dp[(1<<n)-1][m] == 0) printf("No solution\n"); else { int tmp = gcd(f[n],dp[(1<<n)-1][m]); printf("%d/%d\n",f[n]/tmp, dp[(1<<n)-1][m]/tmp); } } return 0; }
ZOJ-3777-Problem Arrangement(状态DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。