设为首页 加入收藏

TOP

Acwing 327. 玉米田
2023-07-23 13:39:18 】 浏览:117
Tags:Acwing 327. 米田

算法分析

棋盘型状态压缩dp

这类dp有一个通用的状态表示法:f[i][j][k],表示前i行(放了j个棋子后)的状态表示为k。

由于本题无棋子要求,因此可以省去中间一维,
即:
??用f[i][j]表示前i行土地的状态为j。


首先由于玉米地有不肥沃的地方不能种植,因此需要通过二进制表示出来可以种植和不可以种植的地方,
我们是将整行用一个二进制数表示的,可种为0,不可种为1,在输入的时候即可判断:
??g[i] += (!x<<(j-1)) //g[i]为每一行土地的二进制表示
由于是棋盘型,因此根据我们的经验显而易见可以知道需要分别分析棋盘的列和行:

根据题意相邻的两格内不能同时种玉米可知:
??(以x为当前格)则 ?(x&x>>1)=0;
?? 这很容易理解,比如x的二进制表示为1101,则x>>1 = 0110,可以得出x&x>>1的结果和题目要求相同;

再分析每一列,由于上下列不能同时种玉米:
??(y为相同列不同行的玉米地)因此(y&y-1)=0;



T.T好累
先看代码吧:

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N=13,mod = 1e8;
int f[N][1<<N];
int g[N];
vector<int> state;
vector<int> le_state[1<<N];
bool check(int x)
{
    return !(x&x>>1);
}

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            int x;
            scanf("%d",&x);
            g[i]+=(!x<<(j-1));   
            cout<<g[i]<<endl;
        }
    }
    
    for(int i=0;i<(1<<m);i++) {
        if(check(i)) {
            state.push_back(i);
        }
    }
    
    for(int i=0;i<state.size();i++) {
        for(int j=0;j<state.size();j++) {
            if(!(state[i]&state[j])) {
                le_state[i].push_back(j);
            }
        }
    }
    
    f[0][0]=1;
    for(int i=1;i<=n+1;i++) {
        for(int j=0;j<state.size();j++) {
            if(state[j]&g[i]) continue;
            for(int b=0;b<le_state[j].size();b++) {
                f[i][j] = (f[i][j] + f[i-1][le_state[j][b]])%mod;
            }
        }
    }
    
    cout<<f[n+1][0];
    return 0;
}
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇C++内存分区模型 下一篇C++学习-const

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目