bzoj4806 炮——DP
2024-08-31 11:10:13
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=4806
看到这题首先会想到状压什么乱七八糟的,然而很难做;
其实,因为求的是方案数,所以并不需要关注炮摆放的位置,而只需要关注数量;
f[i][j][k] 表示第 i 行及以前共有 j 个有 0 炮的列和 k 个有 1 炮的列,就可以转移了。
代码如下:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
int const mod=,maxn=;
ll n,m,f[maxn][maxn][maxn],ans;
ll C(ll x){return ((x-)*x/)%mod;}//不是(x+1) !!
int main()
{
scanf("%d%d",&n,&m);
f[][m][]=;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)//
for(int k=;k<=m-j;k++)//
{
(f[i][j][k]+=f[i-][j][k])%=mod;//放0个
if(k>=&&j<m)(f[i][j][k]+=f[i-][j+][k-]*(j+))%=mod;//0 -> 1 //别写成 if(k&&j<m) !!
if(k<m)(f[i][j][k]+=f[i-][j][k+]*(k+))%=mod;//1 -> 2
if(j<m)(f[i][j][k]+=f[i-][j+][k]*(j+)*k)%=mod;//0 1 -> 1 2
if(k->=&&j+<=m)(f[i][j][k]+=f[i-][j+][k-]*C(j+))%=mod;//0 0 -> 1 1
if(k+<=m)(f[i][j][k]+=f[i-][j][k+]*C(k+))%=mod;//1 1 -> 2 2
}
for(int j=;j<=m;j++)
for(int k=;k<=m;k++)
(ans+=f[n][j][k])%=mod;
printf("%lld",ans);
return ;
}
最新文章
- [转]通过Visual Studio为Linux编写C++代码
- es let2
- Java和C#语法对比
- int long 等基础类型在不同平台的大小
- Swing开发之JComboBox篇
- Hive介绍、安装(转)
- 正向代理VS反向代理 总结
- 洛谷P2014 TYVJ1051 选课
- JAVA 继承 extends
- 图片裁切插件jCrop的使用心得(四)
- Object.prototype.toString.call() 区分对象类型(判断对象类型)
- 吞吐量(Throughput)、QPS、并发数、响应时间(RT)对系统性能的影响
- PRINCE2的国际形势?光环国际项目管理培训
- Oracle存储过程经典入门
- Ubuntu on win10
- underscore.js源码解析【数组】
- 2018-2019-2 《网络对抗技术》Exp0 Kali安装 Week1 20165320
- Ubuntu下好的PDF阅读器介绍
- php正则替换双引号里面的字符
- TextView
热门文章
- Linux 修改主机名
- Linux核心参数Shmmax,shmall,shmni
- 前端接收到的json的属性的首字母会自动变成小写,解决办法如下
- 匈牙利游戏(codevs 1269)
- [NOIP1998] 普及组
- POJ3233:Matrix Power Series
- httpclient自动执行http的302重定向
- 离线配置Anaconda3+tensorflow-gpu1.4.0+cuda8.0+cudnn6.0
- QT程序--小工具集合
- 拷贝地图 CopyAndOverwriteMap()