第一次写题解，有点紧张，有错误请巨巨们轻喷～～

题目描述

问一个最多n行m列的一个棋盘最多能有多少种放置k个棋子的方法。（其中n是小于等于6的）

题目分析

我们首先将问题化简一下，首先考虑一个n行m列的棋盘最多能有多少种摆放方式，能够不发生冲突。如果采用dfs的思想我们是一定会超时的，此时一看n是小于6的那么我们就可以采用状态压缩递推出方法数。
然后我们此时一看他的限制条件，是一个日字型，与前面两列都是有关的，所以我们的状态至少要保持前面两列的状态。
思考完这些我们便可以推算出全部的摆放方式，在来思考摆放的个数限制条件，我们可以在加一个维度来记录即可。
下面是ac代码，在关键点会加注释^.^。

C++ 代码

#include<iostream>
using namespace std;
const int N=1<<12;//保留前两列需要2*6的大小来保存
const int mod=1e9+7;//模数
const int M=1e2+7;
const int T1=30;
typedef long long ll;//int肯定会爆精度，所以要使用ll
ll dp[M][N][T1];//dp[i][j][k] i代表当前列，j代表当前状态，k代表以及含有k个棋子 dp[i][j][k]代表以有方案数
int lowit(int x){//计算当前行状态能增加多少个棋子
    int sum=0;
    for(;x;x-=(x&-x))sum++;
    return sum;
}
int n,m,T;
int maxn,maxnt;//记录表示所有状态的最大值
int main(){
    cin>>n>>m>>T;
    dp[0][0][0]=1;
    maxn=1<<(n<<1);maxnt=1<<n;
    for(int i=1;i<=m;i++)//m行递推
        for(int j=0;j<maxn;j++){//枚举当前行与前面一行所有状态
            int a=j%maxnt,b=j/maxnt;//a为当前行状态 b为前面一行状态
            if(((a<<2)&b)||(b&(a>>2)))continue; //如果当前行和前面一行以及发生冲突则直接跳过剪枝
            int t=lowit(a);//计算当前行的棋子个数
            for(int k=0;k<maxnt;k++)//枚举往前数第二行的状态，将前面两行拼接
                if((k>>1)&a||(a>>1)&k)continue;//只需要比对当前行和该行的信息，前面如果发生冲突答案必定为0
                else{
                    for(int c=t;c<=T;c++)//背包问题,将棋子数加入到我们计算的好的状态当中
                        dp[i][j][c]=(dp[i][j][c]+dp[i-1][(k<<n)+b][c-t])%mod;
                }
        }
    ll sum=0;
    for(int i=0;i<maxn;i++)
        sum=(sum+dp[m][i][T])%mod;
    cout<<sum;
}

我又来补题解了，上一个写的太烂了。

#include<iostream>
using namespace std;
const int N=1<<6;
const int M=110;
const int T=30;
const int mod=1e9+7;
typedef long long ll;
ll f[M][N][N][T];//f[i][a][b][t] i 代表前i列 a代表前前列，b代表前面一列的状态集合 t代表已经用过多少个棋子
int lowit(int x){//计算当前列增加了多少个棋子
    int res=0;
    for(;x;x-=(x&-x))res++;
    return res;
}
int main(){
    int n,m,k;
    cin>>n>>m>>k;
    int maxn=1<<n;
    f[0][0][0][0]=1;//初始化
    for(int i=1;i<=m;i++)
        for(int a=0;a<maxn;a++)
            for(int b=0;b<maxn;b++)
                if((a>>2)&b||a&(b>>2))continue;//判断前前列和前列有没有发生冲突剪枝
                else
                    for(int c=0;c<maxn;c++){
                        if((c>>2)&b||c&(b>>2))continue;//判断前列和当前列有没有发生冲突
                        if((c>>1)&a||c&(a>>1))continue;//判断前前列和当前列有没有发生冲突
                        int t=lowit(c);
                        for(int tt=t;tt<=k;tt++)//背包计算个数
                            f[i][b][c][tt]=(f[i][b][c][tt]+f[i-1][a][b][tt-t])%mod;
                    }
    int res=0;
    for(int i=0;i<maxn;i++)//对前前列和前列不同的状态最终有多少个可以摆放的方案数
        for(int j=0;j<maxn;j++)
            res=(res+f[m][i][j][k])%mod;
    cout<<res;
}