题目描述
在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。
输入格式
只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）
输出格式
所得的方案数
样例输入
3 2
样例输出
16
首先预处理出一行里面满足题意的情况
判断的时候使用!(x>>1)&x&&!(x<<1)&x
原理自行研究
设所有情况下标为0到max
用pair保存
first代表状态
second代表里面的国王个数（防止重复运算浪费时间）
然后按行进行DP
dp[i][j][j]代表第i行第j种状态里面有l个国王的情况总数
如果满足八个方向不相邻的话
八个方向不相邻的话只需要判断
(y>>1)&x和(y<<1)&x和y&x是不是0
原理自行研究
都不是0就代表可以满足
对应状态转移方程为
\( dp[i][j][l]=\Sigma_{j=0}^{max} dp[i-1][j][l-ans[j].second] \)最后就只需要对每一个状态求和就可以啦！！
dp[0][0][0]千万不要忘记初始化orz
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
/************************************************************************* >>> Author: WindCry1 >>> Mail: lanceyu120@gmail.com >>> Website: https://windcry1.com >>> Date: 11/29/2019 2:41:00 PM *************************************************************************/ #include <cstring> #include <cmath> #include <cstdio> #include <cctype> #include <cstdlib> #include <ctime> #include <vector> #include <iostream> #include <string> #include <queue> #include <set> #include <map> #include <algorithm> #include <complex> #include <stack> #include <bitset> #include <iomanip> #include <list> #include <sstream> #include <fstream> #if __cplusplus >= 201103L #include <unordered_map> #include <unordered_set> #endif #define ll long long #define ull unsigned long long using namespace std; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const double clf = 1e-8; const int MMAX = 0x7fffffff; const int INF = 0x3f3f3f3f; const int mod = 1e9+7; const int dir[4][2]={-1,0,1,0,0,-1,0,1}; ostream& operator <<(ostream &out, pii &p){ return out<<p.first<<" "<<p.second; } istream& operator >>(istream &in, pii &p){ return in>>p.first>>p.second; } vector<pii> ans; int n,k; ll dp[110][1<<10][110]; inline void init(){ for(int i=0;i<(1<<n);i++){ if(i&(i>>1)) continue; int cnt=0; for(int j=i;j!=0;j>>=1) cnt+=(j&1); ans.emplace_back(i,cnt); } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); //freopen("C:\\Users\\LENOVO\\Desktop\\in.txt","r",stdin); //freopen("C:\\Users\\LENOVO\\Desktop\\out.txt","w",stdout); cin>>n>>k; init(); dp[0][0][0]=1; ll res=0; for(int i=1;i<=n;i++){ for(int j=0;j<ans.size();j++){ for(int l=0;l<=k;l++){ if(l>=ans[j].second){ for(int t=0;t<ans.size();t++){ if(!(ans[t].first&ans[j].first)&&!(ans[t].first&(ans[j].first<<1))&&!(ans[t].first&ans[j].first>>1)) dp[i][j][l]+=dp[i-1][t][l-ans[j].second]; } } } } } for(int i=0;i<ans.size();i++) res+=dp[n][i][k]; cout<<res<<endl; return 0; } |
2019-11-30 19:18 Author: WindCry1
0 条评论