G - Tray Bien 题意：给你m * 3的矩形范围内，有一些格子是坏掉的，求用1 * 1和1 * 2来填满这个矩形的方案数。 题解： dp[i][s] 代表第i列，状态为s的方案数。 用1代表被填，0代表没有被填。 dp[i][s]由dp[i-1][t] 转移而来，因为本题固定三行，所以状态总数为8。 然后理解如何转移 s1 s2 0 0 0 1 1 1 设s1为之前状态，s2为现在状态。如果你发现当前状态此位为0，之前的状态此位也为0，那么现在的状态肯定不合法，因为我们需要填满之前的所有格子。 s1 s2 0 1 0 1 1 1 如果现在状态此位为1，之前状态此位为0，那么我们需要横着放1*2的，就意味着这位的贡献没了，就是11的组合。
#include<bits/stdc++.h> #define ll long long using namespace std; int sta[50]; ll dp[50][10]; int main() { int m,n; scanf("%d%d",&m,&n); memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) { double x,y; scanf("%lf%lf",&x,&y); sta[(int)x] |= ( 1 << ( (int) y ) ) ; } for(int i=0;i<8;i++) { if((i&sta[0])==0) { if(i==3||i==6) dp[0][i] = 2; else if(i==7) dp[0][i] = 3; else dp[0][i] = 1; } } for(int i=1;i<m;i++) { for(int s1=0;s1<8;s1++) { for(int s2=0;s2<8;s2++) { int f = 0; for(int j=0;j<3;j++) { if((s1&(1<<j))==0&&(s2&(1<<j))==0&&(sta[i-1]&(1<<j))==0) { f = 1; break; } } if(f || (s2 & sta[i]) ) continue ; int now = s2 ; for(int j=0;j<3;j++) { if((s1&(1<<j))==0&&(sta[i-1]&(1<<j))==0) now ^= (1<<j); } ll res ; if(now == 6 || now == 3) res = 2; else if(now == 7) res = 3; else res = 1; dp[i][s2] += dp[i-1][s1] * res; } } } printf("%lld\n",dp[m-1][sta[m-1]^7]); }