//hoj 2662 Pieces Assignment//有一个n*m的棋盘(n、m≤80,n*m≤80)要在棋盘上放k(k≤20)个棋子，使得任意两//个棋子不相邻（每个棋子最多和周围4个棋子相邻）。求合法的方案总数。////算是另一个状态压缩dp入门吧//dp[i][S][j]表示第i行的棋子状态是S(整数的二进制形式，比如5为// …101,省略号表示前导0，那一位上是1就表示哪一列上放了棋子，5表示第一列//第三列放了棋子。)时已经放了j颗棋子，则转移方程为：//dp[i][S][j] = sigma(dp[i-1][V][j-get(V)])//dp[i-1][V][j-get(V)]表示第i-1行的棋子状态是V时已经放了j-get(V)颗棋子//get(V)表示V状态下的放了棋子的个数//在求get(V)时，本身就要判断V是否合法，所以用到了一个S，，有些巧妙//最后sigma(dp[n][S][k])就是我们所求的答案。//这题在刚开始的时候完全不会处理，只知道有四重循环，对细节的处理不到位//导致wa了无数发，哎，继续练吧。。。#include <algorithm>#include <bitset>#include <cassert>#include <cctype>#include <cfloat>#include <climits>#include <cmath>#include <complex>#include <cstdio>#include <cstdlib>#include <cstring>#include <ctime>#include <deque>#include <functional>#include <iostream>#include <list>#include <map>#include <numeric>#include <queue>#include <set>#include <stack>#include <vector>#define ceil(a,b) (((a)+(b)-1)/(b))#define endl '\n'#define gcd __gcd#define highBit(x) (1ULL<<(63-__builtin_clzll(x)))#define popCount __builtin_popcountlltypedef long long ll;using namespace std;const int MOD = 1000000007;const long double PI = acos(-1.L);template<class T> inline T lcm(const T& a, const T& b) { return a/gcd(a, b)*b; }template<class T> inline T lowBit(const T& x) { return x&-x; }template<class T> inline T maximize(T& a, const T& b) { return a=a<b?b:a; }template<class T> inline T minimize(T& a, const T& b) { return a=a<b?a:b; }ll dp[85][1<<9][30];int n,m,k;int get(int x){int i=0,s=0;while(x){if (s&&(x&1))return -1;if (s = (x&1))i++;x>>=1;//i++;}return i;}void solve(){memset(dp,0,sizeof(dp));dp[0][0][0] = 1;for (int i=1;i<=n;i++){for (int j=0;j<=k;j++){for (int S=0;S<(1<<m);S++){int t = get(S);if (t==-1||t>j)continue;for (int V=0;V<(1<<m);V++){if (get(V)==-1||(V&S))continue;dp[i][S][j] +=dp[i-1][V][j-t];}}}}ll ans = 0;for (int i=0;i<(1<<m);i++)ans += dp[n][i][k];printf("%lld\n",ans);}int main() {freopen("G:\\Code\\1.txt","r",stdin);while(scanf("%d%d%d",&n,&m,&k)!=EOF){if (n<m)swap(n,m);solve();}return 0;}
要想捉大鱼，不能怕水深。要想摘玫瑰，就得不怕刺。
