【每日一题】德玛西亚万岁

德玛西亚万岁

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

solution

状压dp。

用数字来表示一行方案,对于一个状态x,如果x的第i位(二进制下)为1,表示这一行的第i个位置安排士兵。否则表示不安排士兵。

先把每一行可能的状态都搜出来,也就是在满足相邻两个二进制位不都为1的条件下,搜出所有的方案。可以发现一行的方案数最多不超过400。

然后将两个可以转移的状态之间两两连边。x可以转移到y表示的意思是x这个状态可以和y这个状态相邻。判断两个状态之间能不能转移显然就是看x和y是不是有某个二进制位同时为1,即只有时,x可以转移到y。

表示前i行,第行的状态是y的方案数,注意到,第i行的状态可以是y的前提是y这个状态与所给地形之间不存在某个二进制位置i满足(b表示第i行的地形状态)。。

考虑转移就从所有的转移过来就行了。转移的条件是j这个状态与k这个状态之间有边。

code

/*
* @Author: wxyww
* @Date:   2020-06-02 19:42:43
* @Last Modified time: 2020-06-02 19:54:25
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 1010,mod = 100000000;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1; c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0'; c = getchar();
    }
    return x * f;
}
int a[N],ma[N][N],f[20][N],n,m,b[20];

void solve() {    
    int cnt = 0;
    for(int i = 0;i < (1 << m);++i) {
        int flag = 0;
        for(int j = 1;j < m;++j) {
            if((i >> j & 1) && (i >> (j - 1) & 1)) {flag = 1;break;}
        }
        if(!flag) a[++cnt] = i;
    }

    memset(b,0,sizeof(b));
    for(int i = 1;i <= n;++i) {
        for(int j = 0;j < m;++j) {
            int x = read() ^ 1;
            b[i] |= x << j;
        }
    }

    memset(ma,0,sizeof(ma));
    for(int i = 1;i <= cnt;++i) {
        for(int j = i;j <= cnt;++j) {
            if(!(a[i] & a[j])) ma[i][j] = ma[j][i] = 1;
        }
    }
    memset(f,0,sizeof(f));
    f[0][1] = 1;
    // cout<<ma[1][2]<<endl;
    for(int i = 1;i <= n;++i) {
        for(int j = 1;j <= cnt;++j) {
            if(a[j] & b[i]) continue;
            // if(i == 1 && j == 1) puts("!!!");
            for(int k = 1;k <= cnt;++k) {
                if(ma[k][j]) {
                    // if(k == 1 && i == 1) puts("!!!");
                    f[i][j] += f[i - 1][k],f[i][j] %= mod;
                }
            }
        }
    }
    ll ans = 0;
    for(int i = 1;i <= cnt;++i) 
        ans += f[n][i],ans %= mod;
    cout<<ans<<endl;
}

int main() {
    while(~scanf("%d%d",&n,&m))
    solve();
    return 0;
}
全部评论

相关推荐

07-04 21:23
已编辑
东莞城市学院 后端
秋招和春招只收到几个中大厂的笔试,本人比较菜,感觉大厂的笔试太难,算法题不能全部做出来就没过了,但是CVTE和小天才的感觉不是很难,基本上都做出来了,笔试还是挂了。Boss上投了Java后端开发都没有回音,boss上有面试机会都是C#工控软件开发方向的,但是这个方向不太懂,资料又少,面试的表现有点差,现在还是想看看Java这边,面试的时候比较有把握点。想请教一下,这份简历还有什么问题,一直没什么机会,还有什么地方要修改的。
程序员小白条:学历太差,民办和公办,外包还得区分的,这个学历+这个简历,没的办法,除非你有人脉,太难了,这环境,何况你都毕业了,连一段实习都没,肯定没公司会挑选了,没竞争力,开发才招几个人,跟你竞争的可不是二本,三本的人哦,何况你在二本,三本里面也排名不高
投递小天才等公司7个岗位
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

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