洛谷 P2051 [AHOI2009] 中国象棋 题解

article/2024/4/13 14:20:58

Announcement

  • Programmed on 2024/3/1
  • Written on 2024/3/1

题目来源

  • 洛谷 P2051

Description

给定一个 n × m n\times m n×m 的棋盘,需要放置若干棋子,使得每行、每列至多只有 2 2 2 个棋子,求放置棋子的方案数。

  • 1 ≤ n , m ≤ 100 1\le n,m\le100 1n,m100

Solution

首先想到动态规划,考虑如何设计动态规划的状态。

由于对于放置棋子问题一般按照“行”来转移,因此对于行的限制很容易实现。

于是考虑存储有关列的限制的信息。

那么我们可以令 f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k] 表示前 i i i 行中,已经放置了 j j j 列只有一个棋子的列和 k k k 列有两个棋子的列(即有 m − j − k m-j-k mjk 个空列)。

考虑如何进行转移。分类讨论:

  1. 一个棋子都不放:

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

  1. 把一个放在空列:

f [ i ] [ j ] [ k ] + = f [ i − 1 ] [ j − 1 ] [ k ] ∗ ( m − ( j − 1 ) ∗ k ) f[i][j][k]+=f[i-1][j-1][k]*(m-(j-1)*k) f[i][j][k]+=f[i1][j1][k](m(j1)k)

  1. 把一个放在非空列:

f [ i ] [ j ] [ k ] + = f [ i − 1 ] [ j + 1 ] [ k − 1 ] ∗ ( j + 1 ) f[i][j][k]+=f[i-1][j+1][k-1]*(j+1) f[i][j][k]+=f[i1][j+1][k1](j+1)

  1. 把两个都放在不同空列:

f [ i ] [ j ] [ k ] + = f [ i − 1 ] [ j − 2 ] [ k ] ∗ C m − ( j − 2 ) − k 2 f[i][j][k]+=f[i-1][j-2][k]*C_{m-(j-2)-k}^2 f[i][j][k]+=f[i1][j2][k]Cm(j2)k2

  1. 把一个放在空列、一个放在非空列:

f [ i ] [ j ] [ k ] + = f [ i − 1 ] [ j ] [ k − 1 ] ∗ ( m − j − ( k − 1 ) ) ∗ j f[i][j][k]+=f[i-1][j][k-1]*(m-j-(k-1))*j f[i][j][k]+=f[i1][j][k1](mj(k1))j

  1. 把两个放在不同的非空列:

f [ i ] [ j ] [ k ] + = f [ i ] [ j + 2 ] [ k − 2 ] ∗ C j + 2 2 f[i][j][k]+=f[i][j+2][k-2]*C_{j+2}^2 f[i][j][k]+=f[i][j+2][k2]Cj+22

初始化 f [ 0 ] [ 0 ] [ 0 ] = 1 f[0][0][0]=1 f[0][0][0]=1,答案为 ∑ i = 0 m ∑ j = 0 m − i f [ n ] [ i ] [ j ] \sum\limits_{i=0}^m\sum\limits_{j=0}^{m-i}f[n][i][j] i=0mj=0mif[n][i][j]

Conclusion

  • 对于有限制的棋盘放置问题,一般考虑按照行来转移。
  • 若无法状压且不关心顺序,可以用“符合条件的数量”来转移。

Code

#include <bits/stdc++.h>
using namespace std;
const int p=9999973;
int n,m;
long long f[105][105][105]; // f[i][j][k]-前i行有j列有1个棋子,k列2个棋子的方案数
int calc(int x){ // C_x^2return x*(x-1)/2%p;
}
int main(){scanf("%d%d",&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-1][j][k])%=p; // 不放if (j>=1) (f[i][j][k]+=f[i-1][j-1][k]*(m-(j-1)-k)%p)%=p; // 放一个在空列if (k>=1) (f[i][j][k]+=f[i-1][j+1][k-1]*(j+1)%p)%=p; // 放一个在非空列if (j>=2) (f[i][j][k]+=f[i-1][j-2][k]*calc(m-(j-2)-k)%p)%=p; // 放2个在不同空列if (k>=1) (f[i][j][k]+=f[i-1][j][k-1]*(m-j-(k-1))*j%p)%=p; // 放1个在空列、1个在非空列if (k>=2) (f[i][j][k]+=f[i-1][j+2][k-2]*calc(j+2)%p)%=p; // 放2个在2个非空列}int ans=0;for (int i=0;i<=m;i++) for (int j=0;j<=m-i;j++) (ans+=f[n][i][j])%=p;printf("%d\n",ans);return 0;
}

http://www.ngui.cc/article/show-1927523.html

相关文章

【力扣】两数相加,模拟 + 递归

两数相加原题地址 方法一&#xff1a;模拟 注意到链表的方向是从低位到高位&#xff0c;而做“竖式相加”也是低位到高位。以下算式中&#xff0c;若表示成链表&#xff0c;都是从右往左的。 1 2 3 <- l14 5 <- l2 --------------1 6 8 所以可以用同样的方法来模…

【算法设计与分析】和相等的子数组

&#x1f4dd;个人主页&#xff1a;五敷有你 &#x1f525;系列专栏&#xff1a;算法分析与设计 ⛺️稳中求进&#xff0c;晒太阳 题目 给你一个下标从 0 开始的整数数组 nums &#xff0c;判断是否存在 两个 长度为 2 的子数组且它们的 和 相等。注意&#xff0c;这两个…

在实训云平台上配置云主机

文章目录 零、学习目标一、实训云升级二、实训云登录&#xff08;一&#xff09;登录实训云&#xff08;二&#xff09;切换界面语言&#xff08;三&#xff09;规划云主机实例 三、创建网络三、创建路由器2024-2-29更新到此四、添加接口五、创建端口六、添加安全组规则七、创建…

MySQL(基础篇)——函数、约束

一.函数 1.定义 函数是指一段可以直接被另一段程序调用的程序或代码。 2.字符串函数 常见如下&#xff1a; -- 字符串拼接 SELECT CONCAT(hello,MySql) AS CONCAT -- 将字符串全部转为小写 SELECT LOWER(HEllo MYSql) AS LOWER -- 将字符串全部转为大写 SELECT UPPER(Hello…

SpringCloud搭建微服务之Consul服务注册与发现

1. Consul介绍 Consul是由HashiCorp公司使用Go语言开发的一款开源工具&#xff0c;主要用于实现分布式系统的服务发现和服务配置&#xff0c;其内置了服务注册与发现框架、分布式一致性协议实现、健康检查、Key-Value存储、多数据中心方案。Consul具有高可移植性&#xff0c;支…

c# Excel转换成DataSet

/// <summary> /// Excel转换成DataSet&#xff08;.xlsx/.xls&#xff09; /// </summary> /// <param name"filePath">Excel文件路径</param> /// <param name"strMsg"></param> …

大街款商城项目03-微服务之间调用

目录 RestTemplate OpenFeign 1.引入依赖open-feign 2.声明要调用的服务和接口 3.注入FeignClient启用 4验证 RestTemplate 在微服务架构中&#xff0c;使用RestTemplate是一种常见的方式进行服务间的HTTP通信。以下是一个简单的示例&#xff0c;演示如何使用RestTempla…

嵌入式LINUX移植、配置ssh

编译 https://quantum6.blog.csdn.net/article/details/136299665 编译时指定prefix&#xff0c;产生的文件会自带这个目录。所以直接忽略。 ./configure# 不指定编译路径&#xff0c;手动复制。 复制 编译后的整个目录打包&#xff0c;复制到开发板。写个脚本&#xff0c…

k8s学习-数据管理之nfs手动搭建

需要先准备好3台虚拟机 系统CentOS7 IP 192.168.200.128 master IP 192.168.200.129 node1 IP 192.168.200.130 node2 问题描述 在学习数据管理的时候创建完pv和pvc以后&#xff0c;创建了pod使用pvc&#xff0c;但是pod创建不成功。 查看pod描述 kubectl describe pod myp…

最新消息:英特尔宣布成立全新独立运营的FPGA公司——Altera

今天&#xff0c;英特尔宣布成立全新独立运营的FPGA公司——Altera&#xff08;2015年6月Intel以 167 亿美元的价格&#xff0c;收购FPGA厂商Altera&#xff09;。首席执行官Sandra Rivera和首席运营官Shannon Poulin分享展示其在超过550亿美元的市场中保持领先性的战略规划&am…