P2051 [AHOI2009]中国象棋 大力DP
2024-09-25 09:30:35
状压个啥$qwq$
思路:大力$DP$
提交:2次(自信的开了$int$)
题解:(见注释)
#include<cstdio>
#include<iostream>
using namespace std;
#define ull unsigned long long
#define ll long long
#define R register ll
#define pause (for(R i=1;i<=10000000000;++i))
#define In freopen("NOIPAK++.in","r",stdin)
#define Out freopen("out.out","w",stdout)
namespace Fread {
static char B[<<],*S=B,*D=B;
#ifndef JACK
#define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)
#endif
inline int g() {
R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;
if(ch==EOF) return EOF; do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;
} inline bool isempty(const char& ch) {return (ch<=||ch>=);}
inline void gs(char* s) {
register char ch; while(isempty(ch=getchar()));
do *s++=ch; while(!isempty(ch=getchar()));
}
} using Fread::g; using Fread::gs;
const int N=,M=;
int n,m,ans;
ll f[N][N][N];
//f[i][j][k]:所处行编号i,含有一个棋子的列数j,含有两个棋子的列数k
signed main() {
n=g(),m=g(); f[][][]=;
for(R i=;i<=n;++i) for(R j=;j<=m;++j) for(R k=;k<=m-j;++k){
f[i][j][k]+=f[i-][j][k];
//不填棋子
if(j>=) f[i][j][k]+=f[i-][j-][k]*(m-k-j+);
//选空列填一个棋子
if(k>=) f[i][j][k]+=f[i-][j+][k-]*(j+);
//选含有一个棋子的某列
if(j>=) f[i][j][k]+=f[i-][j-][k]*(m-k-j+)*(m-k-j+)/;
//选两个空列分别填一个棋子
if(k>=) f[i][j][k]+=f[i-][j][k-]*(m-k-j+)*j;
//选一个空列和含有一个棋子的某列分别填一个棋子
if(k>=) f[i][j][k]+=f[i-][j+][k-]*(j+)*(j+)/;
//选含有一个棋子的某两列分别填一个棋子
f[i][j][k]%=M;
} for(R j=;j<=m;++j) for(R k=;k<=m-j;++k) ans=(ans+f[n][j][k])%M;
printf("%d\n",ans);
}
2019.07.17
最新文章
- C# - 多线程 之 信号系统
- 通过程序 VB.Net 或 C# 读取文本文件行数
- coreseek安装使用
- SpringMVC入门一:helloWorld
- 判断两个XML文件结构与内容是否相同
- C++ Opencv Mat类型使用的几个注意事项及自写函数实现Laplace图像锐化
- JAVA多线程之当一个线程在执行死循环时会影响另外一个线程吗?
- 关于dede后台登陆后一片空白以及去除版权
- WebLogic使用总结(七)——WebLogic部署Web应用并绑定域名
- Oozie-自定义实现WorkFlow中shell action
- 『C++』Temp_2019_03_14 不同类的循环引用
- Percona Toolkit工具集介绍
- log4cpp基础测试
- Java BigInteger 与C# BigInteger之间的问题
- windows游戏开发中一个关于Visual Studio的编译链接成功,输出窗口却显示线程已退出。无法运行项目的问题
- L2-3 名人堂与代金券 (25 分)
- python之operator操作符函数
- poj3481(splay tree 入门题)
- sqlplus--spool基础运用
- SINAMICS S120屏蔽报警