国王

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1396 字
在n×n棋盘上放k个国王，国王攻击周围8个格
一本通
例
正文

/*
原题：T1592 「一本通 5.4 例 1」国王 (SGU 223)
题意：在 n×n 棋盘上放 k 个国王，国王攻击周围 8 个格子，求互不攻击的放置方案数。
思路：按行状压。每行合法状态为相邻两位不同时为 1（行内不相邻）。
     上下两行状态 s,t 需满足 s&t==0 且 (s<<1)&t==0 且 (s>>1)&t==0（不共列、不共对角线）。
     用 dp[当前行状态][已放国王数] 接力转移，累加合法方案。
复杂度：时间 O(n·S²·k)，空间 O(S·k)，S 为合法行状态数（n≤10 时 S≤144）。
易错点：1) 国王攻击含对角线，需同时检查左右移位后的与运算；
       2) 首行没有上一行的限制；3) 若 k 超过最大可放数答案自然为 0。
*/
#include <bits/stdc++.h>
using namespace std;
int n,k;
vector<int> st;   // 合法行状态
vector<int> sc;   // 对应状态的国王数
bool ok(int a,int b){
    return (a&b)==0 && ((a<<1)&b)==0 && ((a>>1)&b)==0;
}
int main(){
    if(!(cin>>n>>k)) return 0;
    for(int s=0;s<(1<<n);s++){
        if((s&(s<<1))==0){
            st.push_back(s);
            sc.push_back(__builtin_popcount(s));
        }
    }
    int S=st.size();
    // dp[t][c]：当前行状态为 t、已放 c 个国王的方案数
    vector<vector<long long>> dp(S,vector<long long>(k+1,0));
    for(int i=0;i<S;i++) if(sc[i]<=k) dp[i][sc[i]]=1;
    for(int r=1;r<n;r++){
        vector<vector<long long>> ndp(S,vector<long long>(k+1,0));
        for(int i=0;i<S;i++){
            for(int j=0;j<S;j++){
                if(ok(st[i],st[j])){
                    for(int c=sc[i];c<=k;c++){
                        ndp[i][c]+=dp[j][c-sc[i]];
                    }
                }
            }
        }
        dp=move(ndp);
    }
    long long ans=0;
    for(int i=0;i<S;i++) ans+=dp[i][k];
    cout<<ans<<"\n";
    return 0;
}
国王

正文

一本通·提高篇的其它内容
