首页 > 代码库 > 【vijos】1286 座位安排（状压dp）
【vijos】1286 座位安排（状压dp）
https://vijos.org/p/1286
这题好神不会捉。。。
首先我们知道所有情况有C(n*m, k)种，这个好搞。但是两两不相邻这个有点难搞。。
原来是状压dp。。sigh。
设状态f[i][j][k]表示第i行放置的摆放状态是j放了k个人的方案，那么有
f[i][j][k]=sum{f[i-1][x][k-num[x]]}，当j的人两两不冲突，且j和x的人两两不冲突，num[x]是x状态的人的数量
最后不冲突的数目是sum{f[n][j][k]}，k是题目所给的，j是所有的状态
显然这是可以减小一维的，那么我们用两个数组来组成滚动数组即可。还有一个要注意的地方就是求C(n*m, k)这个要防爆精度（因为，即我们要边乘边除orz且C(80, 20)的数量用longlong不会爆
#include <cstdio>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <algorithm>#include <queue>using namespace std;#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << (#x) << " = " << (x) << endl#define printarr2(a, b, c) for1(_, 1, b) { for1(__, 1, c) cout << a[_][__]; cout << endl; }#define printarr1(a, b) for1(_, 1, b) cout << a[_] << ‘\t‘; cout << endlinline const int getint() { int r=0, k=1; char c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }inline const int max(const int &a, const int &b) { return a>b?a:b; }inline const int min(const int &a, const int &b) { return a<b?a:b; }typedef long long ll;ll f[1<<9][212][2], sum[1<<9], ans;int n, m, k, st[1<<9], cnt;int cal(int x) { int ret=0; while(x) ++ret, x-=(x&-x); return ret;}ll c(ll x, ll y) { ll ret=1; if(x-y>y) y=x-y; for(ll i=x, j=2; i>=y+1; --i) { ret*=i; while(ret%j==0 && j<=x-y) ret/=j, ++j; } return ret;}ll gcd(ll a, ll b) { return b?gcd(b, a%b):a; }int main() { read(n); read(m); read(k); if(m>n) swap(n, m); int all=(1<<m)-1; for1(i, 0, all) if(!(i&(i>>1)||(i&(i<<1)))) { st[++cnt]=i; sum[i]=cal(i); f[i][sum[i]][0]=1; } for1(line, 2, n) { for1(x, 1, cnt) for1(y, 1, cnt) if(!(st[x]&st[y])) { int i=st[x], j=st[y]; for1(z, 0, k) f[i][z+sum[i]][1]+=f[j][z][0]; } for1(x, 1, cnt) { int i=st[x]; for1(z, 0, k) f[i][z][0]=f[i][z][1], f[i][z][1]=0; } } for1(x, 1, cnt) ans+=f[st[x]][k][0]; ll fm=c(n*m, k); ll d=gcd(fm, ans); if(ans) printf("%lld/%lld", fm/d, ans/d); else puts("Impossible!"); return 0;}
背景
快要期中考试了！老师需要hzy帮他排考试的座位。。。
描述
考场里的座位恰好有n行m列，并且恰好有n*m位考生在这个考场里面考试，也就是 说，所有的座位上都有考生。hzy根据学校记载，有k位考生可能作弊，因此hzy不能让他们之中的任何两个人做在相邻的座位上！所谓相邻的座位，即在同一 行相邻列或者在同一列的相邻行的座位。hzy准备这样安排座位，首先随机选择一种方案，如果这种方案是合法的，就用这种方案，否则重新选择。你的任务是计 算，他得到一个合法方案时，需要的期望选择次数。
格式
输入格式
输入文件为一行，仅包含三个整数n，m和k。
输出格式
如果不存在合法的方案，则输出文件seating.out中应该包含Impossible!，否则输出一个分数p/q，表示期望选择次数(即平均次数)，这里p和q应该是互质的。
样例1
样例输入1[复制]
1 4 3
样例输出1[复制]
Impossible!
样例2
样例输入2[复制]
2 3 2
样例输出2[复制]
15/8
提示
1≤n≤80，1≤m≤80，1≤n*m≤80
0≤k≤20，并且k≤n*m
【vijos】1286 座位安排（状压dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。