设为首页 加入收藏

TOP

中国象棋
2019-07-15 12:09:45 】 浏览:78
Tags:中国象棋

中国象棋

题目

【题目描述】

这次小可可想解决的难题和中国象棋有关,在一个N行M列的棋盘上,让你放若干个炮(可以是0个),使得没有一个炮可以攻击到另一个炮,请问有多少种放置方法。

大家肯定很清楚,在中国象棋中炮的行走方式是:一个炮攻击到另一个炮,当且仅当它们在同一行或同一列中,且它们之间恰好 有一个棋子。

你也来和小可可一起锻炼一下思维吧!

【输入格式】

一行包含两个整数N,M,之间由一个空格隔开。

【输出格式】

总共的方案数,由于该值可能很大,只需给出方案数模9999973的结果。

【数据规模】

100%的数据中N和M均不超过100

50%的数据中N和M至少有一个数不超过8

30%的数据中N和M均不超过6

解析

动态规划题。

令f[i][j][k]表示前i行,放一个炮的有j列,放两个炮的有k列,边界为f[0][0][0]=1,,

则状态转移方程有以下几种:

1、不放:f[i][j][k]=f[i][j][k]+f[i-1][j][k];

2、放一个在零个的那列:f[i][j][k]=f[i][j][k]+f[i-1][j-1][k]*(m-j-k+1);

3、放一个在一个的那列:f[i][j][k]=f[i][j][k]+f[i-1][j+1][k-1]*(j+1);

4、分别放一个在一个的两列:f[i][j][k]=f[i][j][k]+f[i-1][j+2][k-2]*(j+1)*(j+2)/2;

5、分别放一个在零个的一列和一个的一列:f[i][j][k]=f[i][j][k]+f[i-1][j][k-1]*j*(m-j-k+1);

6、分别放一个在零个的两列:f[i][j][k]=f[i][j][k]+f[i-1][j-2][k]*(m-j-k+1)*(m-j-k+2)/2。

要注意各种情况的先决条件!最后的答案是所有f[n][j][k]的总和。记得开long long!!!

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;
const int mod=9999973;
int n,m;
long long f[101][101][101],ans;
//f[i][j][k]表示前i行,放一个炮的有j列,放两个炮的有k列 
int main()
{
    memset(f,0,sizeof(f));
    cin>>n>>m;
    f[0][0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
            for(int k=0;k<=m-j;k++)
            {
                f[i][j][k]=(f[i][j][k]+f[i-1][j][k])%mod;//不放
                if(j)//放一个在零个的那列
                    f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k]*(m-j-k+1))%mod;//(m-j-k+1)即原来零个的总列数 
                if(k)//放一个在一个的那列
                    f[i][j][k]=(f[i][j][k]+f[i-1][j+1][k-1]*(j+1))%mod;//(j+1)即原来一个的总列数 
                if(k>=2)//分别放一个在一个的两列
                    f[i][j][k]=(f[i][j][k]+f[i-1][j+2][k-2]*(j+1)*(j+2)/2)%mod;//(j+2)即原来有两列为一个的总列数 
                if(j&&k)//分别放一个在零个的一列和一个的一列
                    f[i][j][k]=(f[i][j][k]+f[i-1][j][k-1]*j*(m-j-k+1))%mod;
                if(j>=2)//分别放一个在零个的两列
                    f[i][j][k]=(f[i][j][k]+f[i-1][j-2][k]*(m-j-k+1)*(m-j-k+2)/2)%mod; 
            }
    for(int j=0;j<=m;j++)
        for(int k=0;k<=m-j;k++)
            ans=(ans+f[n][j][k])%mod;//累加答案     
    cout<<ans;
    return 0;
}
View Code

 

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇我的博客主题来源 下一篇小计C++中的引用和vector

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目