牧场的安排

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1515 字
M行N列牧场，1表示可种草、0表示不可；草不
一本通
例
正文

/*
原题：T1593 「一本通 5.4 例 2」牧场的安排 (USACO Corn Fields)
题意：M 行 N 列牧场，1 表示可种草、0 表示不可；草不能相邻（无公共边），求种植方案数 mod 10^8。
思路：按行状压。每行合法状态 s 需满足：s 只含可种草格(s&原图反码==0) 且 行内无相邻(s&(s<<1)==0)。
     行转移时要求上下两行不重叠(s&t==0)。dp[当前行状态] 累加上一行所有不冲突状态。
复杂度：时间 O(M·S²)，空间 O(S)，S≤2^N（N≤12 时 S≤4096，实际合法状态更少）。
易错点：1) 荒废（一行都不种，s=0）也算合法状态，必须包含；
       2) 取模为 10^8 而非 10^9+7；3) 输入先 M 后 N（行数×列数）。
*/
#include <bits/stdc++.h>
using namespace std;
const int MOD=100000000;
int main(){
    int M,N;
    if(!(cin>>M>>N)) return 0;
    vector<int> fertile(M,0);
    for(int i=0;i<M;i++){
        int row=0;
        for(int j=0;j<N;j++){
            int x; cin>>x;
            if(x) row|=(1<<j);
        }
        fertile[i]=row;
    }
    // 预计算每行的合法状态
    vector<vector<int>> valid(M);
    for(int i=0;i<M;i++){
        for(int s=0;s<(1<<N);s++){
            if((s&fertile[i])==s && (s&(s<<1))==0){
                valid[i].push_back(s);
            }
        }
    }
    // 第 0 行：每个合法状态初始方案数为 1
    vector<long long> dp;
    for(int s:valid[0]) dp.push_back(1);
    for(int r=1;r<M;r++){
        vector<long long> ndp(valid[r].size(),0);
        for(int i=0;i<(int)valid[r].size();i++){
            int s=valid[r][i];
            for(int j=0;j<(int)valid[r-1].size();j++){
                int t=valid[r-1][j];
                if((s&t)==0){
                    ndp[i]=(ndp[i]+dp[j])%MOD;
                }
            }
        }
        dp=move(ndp);
    }
    long long ans=0;
    for(long long x:dp) ans=(ans+x)%MOD;
    cout<<ans<<"\n";
    return 0;
}
牧场的安排

正文

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