欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

牧场的安排(状压dp)

程序员文章站 2022-07-07 20:22:32
...

题目描述

FarmerJohn新买了一块长方形的牧场,这块牧场被划分成M行N列(1≤M≤12;1≤N≤12),每一格都是一块正方形的土地。FJ打算在牧场上的某几格土地里种上美味的草,供他的奶牛们享用。遗憾的是,有些土地相当的贫瘠,不能用来放牧。并且,奶牛们喜欢独占一块草地,于是FJ不会选择两块相邻的土地,即:没有哪两块草地有公共边。当然,FJ还没有决定在哪些土地上种草。
作为一个好奇的农场主,FJ想知道,如果不考虑草地的总块数,那么,一共有多少种种植方案可供他选择。当然,把新的牧场荒废,不在任何土地上种草,也算一种方案。请你帮FJ算一下这个总方案数。

输入描述:

第1行:两个正整数M和N,用空格隔开;
第2到M+1行:每行包含N个用空格隔开的整数,描述了每块土地的状态。输入的第i+1行描述了第i行的土地。所有整数均为0或1,1表示这块土地足够肥沃,0则表示这块地上不适合种草。

输出描述:

第1行:输出一个整数,即牧场分配总方案数除以10^8 的余数。

示例

输入

2 3
1 1 1
0 1 0

输出

9

说明

按下图把各块土地编号:
1 2 3
0 4 0
只开辟一块草地有4种方案:选1,2,3,4中的任一块。开辟两块草地的话,有3种方案:13,14以及34。选三块草地只有一种方案:134。再加把牧场荒废的那一种,总方案数为4+3+1+1=9种。

备注:

1≤N,M≤12。

题目思路:

看到n,m小于或等于12就想到状压dp,因为两块相邻的地不能种草,所以需要预处理一下。
当i表示每行地的状态时,(i<<1)&i)0就表示在这一行没有两块地相邻。
我们可以用一个vector保存每行地合法的状态。
当i表示这一行的状态,j表示上一行的状态时,i&j
0就表示这两行没有地相邻
当i表示这一行的状态,j表示这一行是否可以种草的状态时,i&j==i就说明i状态是可行的,假如i&j!=i,那么就存在i状态的某一列是1,但是这一块地本身是不能种植的。
用一个数组s来保存这一行是否可以种草的状态

以行数作为阶段,本行的状态和上一行的状态作为dp的状态,是否合法作为决策。
dp[i][j]表示第i行j状态时前i行的方案数,dp[0][0] = 1作为边界(都不种也是一种方案)。
状态转移是如果本行的j状态和上一行的k状态不冲突,那么本行j状态的方案数就加上上一行k状态的方案数,说明k状态可以到j状态。
最后统计dp[n][所有状态]的总方案数。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,dp[13][401],a[13][13],s[13];
const int mod = pow(10,8);
vector<int> v;
int main()
{
    cin>>n>>m;
    for(int i = 0;i<1<<m;i++)
        if(((i<<1)&i)==0)
            v.push_back(i);
    for(int i = 1;i<=n;i++)
        for(int j = 0;j<m;j++)
            scanf("%d",&a[i][j]);
    for(int i = 1;i<=n;i++)
        for(int j=0;j<m;++j)
            s[i] = (s[i]<<1)+a[i][j];            
    dp[0][0] = 1;
    for(int i = 1;i<=n;i++)
    {
        for(int j = 0;j<v.size();j++)
        {
            if((v[j]&s[i])==v[j])
            {
                for(int k = 0;k<v.size();k++)
                {
                    if((v[k]&v[j])==0)
                    {
                        dp[i][j]+=dp[i-1][k];
                        dp[i][j]%=mod;
                    }                
                }
            }            
        }
    }
    ll ans = 0;
    for(int i = 0;i<v.size();i++)
        ans = (ans+dp[n][i])%mod;
    cout<<ans;
    return 0;
} 

欢迎关注微信公众号:Java后台开发

致力于分享原创计算机与软件开发知识及SSM、Spring cloud、Redis、微服务等Java后端开发技术
公众号里还有很多开发工具及学习资料

牧场的安排(状压dp)

相关标签: 动态规划 算法