【BZOJ】1801 [Ahoi2009]chess 中国象棋(dp)
2024-10-21 20:32:00
题目
传送门:QWQ
分析
发现我们关心的不是棋子的位置,我们只关心棋子数量就ok。
首先每行每列最多两个棋子。这是显然的。
然后我觉得本题最难的部分就是对行进行讨论,蒟蒻我一直被限制在了对格点讨论。。。。
$dp[i][j][k] $放了前$i$行,有$j$列有1个棋子,有$k$列有2个棋子。转移就很显然了。
代码
#include <bits/stdc++.h>
typedef long long ll;
const int maxn=;const ll MOD=; ll dp[maxn][maxn][maxn];
//dp[i][j][k] 放了前i行,有j列有1个棋子,有k列有2个棋子
ll num(int x){return ll(x)*ll(x-)/;}
using namespace std;
int main(){
int n,m;scanf("%d%d",&n,&m);
dp[][][]=;
for(int i=;i<n;i++){ //放第i+1行
for(int j=;j<=m;j++){
for(int k=;k+j<=m;k++){
dp[i+][j][k]=(dp[i+][j][k]+dp[i][j][k])%MOD;
if(m-j-k>=) dp[i+][j+][k]=(dp[i+][j+][k]+dp[i][j][k]*(m-j-k))%MOD;
if(j>=) dp[i+][j-][k+]=(dp[i+][j-][k+]+dp[i][j][k]*j)%MOD;
if(m-j-k>=) dp[i+][j+][k]=(dp[i+][j+][k]+dp[i][j][k]*num(m-j-k))%MOD;
if(j>=) dp[i+][j-][k+]=(dp[i+][j-][k+]+dp[i][j][k]*num(j))%MOD;
if(m-j-k>= && j>=) dp[i+][j][k+]=(dp[i+][j][k+]+dp[i][j][k]*(m-j-k)*j)%MOD;
}
}
}
ll ans=;
for(int i=;i<=m;i++)
for(int j=;j+i<=m;j++)
ans=(ans+dp[n][i][j])%MOD;
printf("%lld\n",ans);
return ;
}
最新文章
- ASP.NET中的缓存机制
- JS获取文本值
- 『TCP/IP详解——卷一:协议』读书笔记——07
- WEBAPP开发技巧总结
- 在纯HTML的静态网页中添加一段统计网页访问量的JAVA Script代码?
- redsocks 配合iptables设置全局sockts5代理
- javascript实现暂停
- 使用CSS3美化复选框checkbox
- HTTP服务负载均衡总结
- ListView中响应item的点击事件并且刷新界面
- FB面经 Prepare: All Palindromic Substrings
- java的HashCode和equals
- c++11の数据竞争和互斥对象
- Python——Django-manage.py的内容
- 《DSP using MATLAB》Problem 7.24
- JavaWeb连接SQLServer数据库并完成一个登录界面及其功能设计。
- SMB溢出漏洞所需的SMB协议内容
- JN5139 zigbee 资料
- 表表达式,Substring, CharIndex, 多行数据变同一行的用法
- java aop的理解
热门文章
- [sql]java.sql.Types的具体对应值(jdbcType)
- PHP--------微商城实现微信授权登录
- HDU - 5917 水题
- 如果从excel表中导出insert-sql
- Psping 实例
- [转载]LeetCode: Gray Code
- 流程设计器jQuery + svg/vml(Demo1 - 构建设计器UI界面)
- Scrum立会报告+燃尽图(3)选题
- winform messagebox 统一
- IOS中UITableViewCell使用详解