M_sea

洛谷2051 [AHOI2009]中国象棋
题目描述这次小可可想解决的难题和中国象棋有关:在一个N行M列的棋盘上,让你放若干个炮(可以是0个),使得没有一个炮...
扫描右侧二维码阅读全文
08
2018/02

洛谷2051 [AHOI2009]中国象棋

题目描述

这次小可可想解决的难题和中国象棋有关:在一个N行M列的棋盘上,让你放若干个炮(可以是0个),使得没有一个炮可以攻击到另一个炮,请问有多少种放置方法。大家肯定很清楚,在中国象棋中炮的行走方式是:一个炮攻击到另一个炮,当且仅当它们在同一行或同一列中,且它们之间恰好有一个棋子。你也来和小可可一起锻炼一下思维吧!

传送门

算法

那么考虑到每行、每列上最多只能有两个炮,
于是设$f[i][j][k]$为放了前i行有j列有1个棋子有k列有两个棋子的方案数。

然后是长得死的状态转移。有下列几种情况:

  • 不放
  • 放一个炮在有一个炮的一列
  • 放一个炮在原本没有炮的一列上
  • 放两个炮,都放在没有炮的列上
  • 放两个炮,都放在有一个炮的列上
  • 放两个炮,一个放在没有炮的列,一个在有一个炮的列上

然后分情况转移。详见代码。
注意避免负下标。

代码

当然是C++的啦。

#include <bits/stdc++.h>
typedef int mainint;
#define int long long
#define re register
using namespace std;
const int MOD=9999973;
inline int C(int x) { //求C(x,2)
    return x*(x-1)/2;
} 
int f[110][110][110]; //f[i][j][k]表示放了前i行有j列有1个棋子有k列有两个棋子的方案数 
mainint main() {
    int n,m; scanf("%lld%lld",&n,&m);
    f[0][0][0]=1; //边界
    for (re int i=1;i<=n;i++)
        for (re int j=0;j<=m;j++)
            for (re int k=0;k<=m-j;k++) { //DP
                f[i][j][k]=0;
                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);
                if (j>=1&&m-(j-1)-k>=0) f[i][j][k]+=f[i-1][j-1][k]*(m-j-k+1);
                if (j>=2) f[i][j][k]+=f[i-1][j-2][k]*C(m-j-k+2);
                if (k>=2) f[i][j][k]+=f[i-1][j+2][k-2]*C(j+2);
                if (k>=1&&m-j-(k-1)>=0) f[i][j][k]+=f[i-1][j][k-1]*j*(m-j-k+1);
                f[i][j][k]%=MOD;
            }
    int ans=0;
    for (re int i=0;i<=m;i++) //统计答案
        for (re int j=0;j<=m-i;j++) {
            ans+=f[n][i][j];
            ans%=MOD;
        }
    printf("%lld\n",ans);
    return 0;
}
最后修改:2018 年 11 月 09 日 04 : 37 PM

发表评论

1 条评论

  1. ych jr

    哪里长了,,,