洛谷2051 [AHOI2009]中国象棋

算法竞赛 动态规划 思维题
编辑文章

题意

N×MN\times M 的棋盘上放若干个炮,要求不能互相攻击,求方案个数。

其中 N,M100N,M\le 100

题解

将题意转化一下就是每行每列都不能放超过 22 个棋子,那么可以用 f[i][j][k]f[i][j][k] 表示前 ii 行,有 jj 列是有 11 个棋子,有 kk 列是有 22 个棋子的合法方案数。那么没有棋子的列数即为 MjkM-j-k

然后分类讨论。

不放

继承上一步的状态。

f[i][j][k]=f[i1][j][k]f[i][j][k]=f[i-1][j][k]

放一个

可以放在没有棋子的列或有 11 个棋子的列,方案数为可以放的列的个数。

f[i][j][k]+={f[i1][j1][k]×(Mjk+1)f[i1][j+1][k1]×(j+1)f[i][j][k]+=\begin{cases} f[i-1][j-1][k]\times (M-j-k+1) \\ f[i-1][j+1][k-1]\times (j+1) \end{cases}

放两个

可以都放在没有棋子或有 11 个棋子的列上;也可以一个放在没有棋子的列上,一个放在有 11 个棋子的列上。

前两种情况的方案数即为 Cx2C^{2}_{x}xx 为可以放的列的个数。

f[i][j][k]+={f[i1][j2][k]×((mjk+2)×(mjk+1)÷2)f[i1][j+2][k2]×((j+2)×(j+1)÷2)f[i1][j][k1]×j×(mjk+1)f[i][j][k]+=\begin{cases} f[i-1][j-2][k]\times ((m-j-k+2)\times (m-j-k+1)\div 2) \\ f[i-1][j+2][k-2]\times ((j+2)\times (j+1)\div 2) \\ f[i-1][j][k-1]\times j\times (m-j-k+1) \end{cases}

代码

//f[i][j][k]前i行,有j列是有1个棋子,有k列是有2个棋子的合法方案数.

#include<bits/stdc++.h>
#define ha 9999973
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

ll n,m,ans,f[105][105][105];

int main()
{
    n=read(); m=read();
    f[0][0][0]=1;
    for (ll i=1;i<=n;i++)
    {
        for (ll j=0;j<=m;j++)
        {
            for (ll k=0;k<=m-j;k++)
            {
                f[i][j][k]=f[i-1][j][k];
                if (k>=1) f[i][j][k]+=f[i-1][j+1][k-1]*(j+1); //放1个在有1个的列上
                if (j>=1) f[i][j][k]+=f[i-1][j-1][k]*(m-j-k+1); //1;0
                if (j>=2) f[i][j][k]+=f[i-1][j-2][k]*((m-j-k+2)*(m-j-k+1)>>1); //2;0;0
                if (k>=2) f[i][j][k]+=f[i-1][j+2][k-2]*((j+2)*(j+1)>>1); //2;1;1
                if (k>=1) f[i][j][k]+=f[i-1][j][k-1]*j*(m-j-k+1); //2;0;1
                f[i][j][k]%=ha;
            }
        }
    }
    for (ll i=0;i<=m;i++) for (ll j=0;j<=m;j++) ans=(ans+f[n][i][j])%ha;
    printf("%lld",ans);
    return 0;
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空