题意:
一块玉米地,有的位置不能种草,种草的小方格不能有临边. 问有多少种方案.
思路:
状压DP.
dp[ i ][ j ] 表示从上到下处理到第 i 行时, 该行状态为 j 的方案数.
下一行某状态的方案数就是上一行所有合理状态的方案数之和.
注意初始化和最后一行的处理.
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 14;
const int MOD = 1e8;
typedef long long ll;
int pat[MAXN],m,n;
ll dp[MAXN][1<<MAXN];
inline bool valid(int s,int i)
{
return (s & (~pat[i]))?false:true......
阅读全文