[SCOI2005]互不侵犯

预处理一行所有可能的情况
用$dp\left [d \right ]\left [ i\right ]\left [ k \right ]$数组记录第d行，当前状态为$s\left [ i \right ]$，总共放置k个的方案数
复杂度$O\left ( nk4^{n} \right )$

#include<cstdio>
#define LL long long
const int N=10;
int n,m,s[1<<N],w[1<<N],c[1<<N][1<<N],cnt=0;
LL dp[N][N<<2][1<<N],ans=0;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<(1<<n);i++)
        if (!(i&(i<<1))&&!(i&(i>>1))) s[++cnt]=i;
    for(int i=1;i<=cnt;i++)
        for(int k=1;k<=n;k++)
            if (s[i]&(1<<(k-1))) w[i]++;
    for(int i=1;i<=cnt;i++)
        for(int j=1;j<=cnt;j++) if (!(s[i]&s[j]))
            if (!(s[i]&(s[j]<<1))&&!(s[i]&(s[j]>>1))) c[i][j]=1;
    for(int i=1;i<=cnt;i++) dp[1][w[i]][i]=1;
    for(int d=2;d<=n;d++)
        for(int i=1;i<=cnt;i++)
            for(int j=1;j<=cnt;j++) if (c[i][j])
                for(int k=w[i];k<=m-w[j];k++)
                    dp[d][k+w[j]][j]+=dp[d-1][k][i];
    for(int i=1;i<=cnt;i++) ans+=dp[n][m][i];
    printf("%lld",ans);
    return 0;
}