SGU 223

题意:给你n*n的矩形,放k个国王,每个国王不能放在别的国王的8连边上,问你有多少种方法

收获:状态DP,因为每行的放置只会影响下一行,然我们就枚举每行的状态和对应的下一行的状态,当两个状态合法时就是可以

转移的时候,然后枚举从第一行到当前行用了多少个,转移一下就行了

#include<bits/stdc++.h>
#define de(x) cout<<#x<<"="<<x<<endl;
#define dd(x) cout<<#x<<"="<<x<<" ";
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define repd(i,a,b) for(int i=a;i>=(b);--i)
#define repp(i,a,b,t) for(int i=a;i<(b);i+=t)
#define ll long long
#define mt(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int,int>
#define pdd pair<double,double>
#define pdi pair<double,int>
#define mp(u,v) make_pair(u,v)
#define sz(a) (int)a.size()
#define ull unsigned long long
#define ll long long
#define pb push_back
#define PI acos(-1.0)
#define qc std::ios::sync_with_stdio(false)
#define db double
#define all(a) a.begin(),a.end()
const int mod = 1e9+;
const int maxn = 1e5+;
const double eps = 1e-;
using namespace std;
bool eq(const db &a, const db &b) { return fabs(a - b) < eps; }
bool ls(const db &a, const db &b) { return a + eps < b; }
bool le(const db &a, const db &b) { return eq(a, b) || ls(a, b); }
ll gcd(ll a,ll b) { return a==?b:gcd(b%a,a); };
ll lcm(ll a,ll b) { return a/gcd(a,b)*b; }
ll kpow(ll a,ll b) {ll res=;a%=mod; if(b<) return ; for(;b;b>>=){if(b&)res=res*a%mod;a=a*a%mod;}return res;}
ll read(){
ll x=,f=;char ch=getchar();
while (ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while (ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
//inv[1]=1;
//for(int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
int n,k;
ll dp[][][];
int dx[] = {,,,-,-,-,,};
int dy[] = {,-,,,-,,-,};
bool ok(int pre,int now){
int arr[][] = {};
rep(i,,n+) arr[][i] = (pre&(<<(i-)));
rep(i,,n+) arr[][i] = (now&(<<(i-)));
rep(i,,) {
rep(j,,n+){
if(arr[i][j]){
int x = i, y = j;
rep(t,,){
int nx = x + dx[t],ny = y + dy[t];
if(arr[nx][ny]) return false;
}
}
}
}
return true;
}
int bit(int s){
bitset<> ans(s);
return ans.count();
}
int main(){
scanf("%d%d",&n,&k);
dp[][][] = ;
rep(i,,n) rep(pre,,<<n) rep(now,,<<n) if(ok(pre,now)){
rep(t,,k-bit(now)+) dp[i+][bit(now)+t][now] += dp[i][t][pre];
}
ll ans = ;
rep(i,,<<n) ans += dp[n][k][i];
printf("%lld\n",ans);
return ;
}

最新文章

  1. 客户有两台windows服务器要做sql server双机切换
  2. java 内核
  3. 接着上一篇 《Is WPF dead》
  4. 11-JS基础
  5. Sql-oracle and sqlserver differences
  6. vs2012 遇到 “此操作要求使用 IIS 集成管线模式。”
  7. POJ2752 Seek the Name,Seek the Fame KMP算法
  8. UVa 10820 (打表、欧拉函数) Send a Table
  9. 用grunt搭建自动化的web前端开发环境-完整教程
  10. 《Mathematical Olympiad——组合数学》——染色问题
  11. Oracle历史记录
  12. 【足迹C++primer】49、超载,变化,运营商
  13. Codeforces 484B Maximum Value(高效+二分)
  14. 南京.NET线下活动后续—一对一技术交流
  15. 导出含有图片的Java项目,图片不显示
  16. hadoop2集群中关键配置文件的记录
  17. 汽车之家汽车品牌Logo信息抓取 DotnetSpider实战[三]
  18. C#导出Excel后关闭进程EXCEL.EXE
  19. SVN不能解锁,报错:没有匹配的可用锁令牌的解决方法
  20. 【题解】Hanoi

热门文章

  1. MapReduce中combine、partition、shuffle的作用是什么
  2. NSTimer解除循环引用
  3. less06 引入(importing)
  4. The evolution of cluster scheduler architectures--转
  5. OpenGL编程逐步深入(十)索引绘制
  6. 滑动切换Activity代码
  7. &lt;Sicily&gt;Polynomial
  8. 昼猫笔记 JavaScript -- 异步执行 | 定时器真的定时执行?
  9. Python中的引用计数法
  10. MAC下搭建appium UI自动化环境