C/C++教程

洛谷 P1879 [USACO06NOV]Corn Fields G

本文主要是介绍洛谷 P1879 [USACO06NOV]Corn Fields G,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

Description

P1879 [USACO06NOV]Corn Fields G

Solution

状压\(dp\) 基础题。

定义状态: \(f[i][j]\) 表示到第 \(i\) 行,且第 \(i\) 行种植状态为 \(j\) 的总方案数。

我们先把每一行的状态记录下来。

枚举每一行,由于当前行的值只能由上一行转移过来,所以枚举当前行状态,再枚举上一行状态。

判断能否进行转移,然后转移即可。

先说判断:设当前行状态为 \(s1\),上一行状态为 \(s2\),那么

  • \(s1\) & \((s1 >> 1)\) == 0,\(s2\) 同理(相邻两位没有都种植的)

  • \(s1\) & \(s2\) == 0,(上下两行对应位没有都种植的)。

  • \((s1 | sta[i]) == sta[i]\),\(s2\) 同理,注意是和 \(sta[i-1]\) 判断。(当前枚举的种植状态是符合当土地条件的)

转移方程: \(f[i][s1] = (f[i][s1] + f[i - 1][s2]) \ \% \ mod\)

这个就很简单了吧,当然要在上述条件都符合的情况下才能转移。

注意:优先级是个很迷的东西,上面我写的判断的式子优先级是有问题的,主要是为了美观,自己写的时候括号能加就加。

Code

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e8;
int n, m;
int sta[13], f[13][1 << 13];

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        for(int j = 1, x; j <= m; j++){
            scanf("%d", &x);
            sta[i] = sta[i] << 1 | x;
        }
    f[0][0] = 1;
    for(int i = 1; i <= n; i++)
        for(int s1 = 0; s1 < (1 << m); s1++)
            for(int s2 = 0; s2 < (1 << m); s2++)
                if(!(s1 & (s1 >> 1)) && !(s2 & (s2 >> 1)) && !(s1 & s2) && (s1 | sta[i]) == sta[i] && (s2 | sta[i - 1]) == sta[i - 1])
                    f[i][s1] = (f[i][s1] + f[i - 1][s2]) % mod;
    int ans = 0;
    for(int i = 0; i < (1 << m); i++)
        ans = (ans + f[n][i]) % mod;
    printf("%d\n", ans);
    return 0;
}

End

这篇关于洛谷 P1879 [USACO06NOV]Corn Fields G的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!