题解 | #[SCOI2005]互不侵犯KING#

[SCOI2005]互不侵犯KING

https://ac.nowcoder.com/acm/problem/20240

本题需要在N*N个棋盘里面摆放上K个国王,国王需要互不侵犯。那么从这个矩阵的角度来看(果断dfs)(开玩笑的。
本题使用状压dp去求解,以每一层作为最外层遍历取走,对于每一层来说哪些格子上放的有国王就是1,没有放国王就是0,所以直接采用二进制去表示每一层的状态。
而到某一层为止到底能放多少国王取决于上一层的状态以及自身不能有侵犯发生。故采用二进制的位运算去判断。
最后状态转移方程为:dp[i][j][st[s].first] += dp[i-1][j-st[s].second][st[t].first];
#include <bits/stdc++.h>

using namespace std;
#define int long long
int dp[10][100][1<<9];
pair<int, int> st[1<<9];
int cnt = 0;
int num(int i) {
    int ans = 0;
    while (i){
        if (i&1==1) ans++;
        i = (i>>1);
    }
    return ans;
}

signed main() {
    int n, k;
    cin>>n>>k;
    dp[0][0][0]=1;
    //将合法的二进制数打表打出来
    for (int i=0;i<(1<<n);i++) {
        if ((i&(i<<1))==0) st[cnt++] = make_pair(i, num(i));
    }
    for (int i=1;i<=n;i++) {
        for (int j=0;j<=k;j++) {
            for (int s=0;s<cnt;s++) {
                if (st[s].second>j) continue;
                for (int t=0;t<cnt;t++) {
                    if (st[s].first&st[t].first) continue;
                    if (st[s].first>>1&st[t].first) continue;
                    if (st[t].first>>1&st[s].first) continue;
                    dp[i][j][st[s].first] += dp[i-1][j-st[s].second][st[t].first];
                }
            }
        }
    }
    int ans = 0;
    for (int t=0;t<cnt;t++) {
        ans += dp[n][k][st[t].first];
    }
    cout<<ans;
    return 0;
}


全部评论
左移右移都可,已经亲测。大佬牛逼,茄汁目前,这个题单的每个题都能看到大佬的题解。虽然有点简略,但代码写的好。
点赞 回复 分享
发布于 2024-10-10 09:29 山东

相关推荐

04-29 22:35
门头沟学院 Java
牛友说改了名字能收到offer:旧图新发查看图片
点赞 评论 收藏
分享
04-21 11:22
已编辑
中华女子学院 UE4
耐心学习_佩可officical:直接举报他,佬,违反劳动法我记得boss会下架
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务