广告：#include <stdio.h>int main(){puts(“转载请注明出处[vmurder]谢谢”);puts(“网址：blog.csdn.net/vmurder/article/details/44022265”);}题解：
一开始让我写这道题，其实我是，是接受的。 BalaBala。 毕竟水题，，都不用特技。
裸状压DP。 直接f[i][j][k]表示第i行状态时j，有k个落子时的方案数。
代码：;int n,m,sum;long long f[N][M][N*N];int str[M],num[M],cnt;bool check(int S,int T){return ((S&T)|(S&(T<<1))|(S&(T>>1)));}int main(){// freopen(“test.in”,”r”,stdin);int i,j,k,l;f[0][1][0]=1;scanf(“%d%d”,&n,&m);sum=1<<n;for(i=0;i<sum;i++){if((i&(i<<1))==0){str[++cnt]=i;k=i,l=0;while(k){l+=(k&1);k>>=1;}num[cnt]=l;}}for(i=1;i<=n;i++){for(j=1;j<=cnt;j++){for(k=1;k<=cnt;k++)if(!check(str[j],str[k])){for(l=num[k];l<=m;l++){f[i][k][l]+=f[i-1][j][l-num[k]];}}}}long long ans=0;for(i=1;i<=cnt;i++)ans+=f[n][i][m];cout<<ans<<endl;return 0;}
分之百的把自己推销给自己。
