当前位置:网站首页>P2592 [zjoi2008] birthday party (DP)
P2592 [zjoi2008] birthday party (DP)
2022-07-01 16:40:00 【Harris-H】
P2592 [ZJOI2008] Birthday party (dp)
dp, The key is how to express the difference between men and women .
So set d p ( i , j , k , l ) dp(i,j,k,l) dp(i,j,k,l) To express with i i i A boy , j j j A girl , The biggest difference between boys and girls is k k k, The biggest difference between girls and boys is l l l.
Then enumerate the quadruple loop dp that will do , Enumerate the boys or girls currently playing .
Time complexity : O ( n m k 2 ) O(nmk^2) O(nmk2)
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<stack>
#include<bitset>
#include<deque>
#include<ctime>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define ri register int
#define il inline
#define fi first
#define se second
#define mp make_pair
#define pairint pair<int,int>
#define mem0(x) memset((x),0,sizeof (x))
#define mem1(x) memset((x),0x3f,sizeof (x))
il char gc()
{
static const int BS = 1 << 22;
static unsigned char buf[BS], *st, *ed;
if (st == ed) ed = buf + fread(st = buf, 1, BS, stdin);
return st == ed ? EOF : *st++;
}
#define gc getchar
template<class T>void in(T &x)
{
x = 0;
bool f = 0;
char c = gc();
while (c < '0' || c > '9')
{
if (c == '-') f = 1;
c = gc();
}
while ('0' <= c && c <= '9')
{
x = (x << 3) + (x << 1) + (c ^ 48);
c = gc();
}
if (f) x = -x;
}
#undef gc
#define pb push_back
#define int ll
#define md 12345678
int n,m,d;
int f[155][155][22][22];
il int max(const int &a,const int &b)
{
return a>b?a:b;
}
signed main()
{
#ifdef M207
freopen("in.in", "r", stdin);
#endif
in(n),in(m),in(d);
f[0][0][0][0]=1;
for(ri i=0;i<=n;++i)
for(ri j=0;j<=m;++j)
for(ri k=0;k<=d;++k)
for(ri h=0;h<=d;++h)
if(f[i][j][k][h])
{
// printf("%lld %lld %lld %lld: %lld\n",i,j,k,h,f[i][j][k][h]);
int tmp=f[i][j][k][h];
(f[i+1][j][k+1][max(h-1,0)]+=tmp)%=md;
(f[i][j+1][max(k-1,0)][h+1]+=tmp)%=md;
}
int ans=0;
for(ri i=0;i<=d;++i)
for(ri j=0;j<=d;++j)
(ans+=f[n][m][i][j])%=md;
printf("%lld",ans);
return 0;
}
边栏推荐
- P2592 [ZJOI2008]生日聚会(dp)
- Principle of motion capture system
- 数据库系统原理与应用教程(004)—— MySQL 安装与配置:重置 MySQL 登录密码(windows 环境)
- VMware 虛擬機啟動時出現故障:VMware Workstation 與 Hyper-v 不兼容...
- 复杂度相关OJ题(LeetCode、C语言、复杂度、消失的数字、旋转数组)
- Stonedb is building blocks for domestic databases, and the integrated real-time HTAP database based on MySQL is officially open source!
- 为国产数据库添砖加瓦,StoneDB 一体化实时 HTAP 数据库正式开源!
- Building blocks for domestic databases, stonedb integrated real-time HTAP database is officially open source!
- 数据库系统原理与应用教程(005)—— yum 离线安装 MySQL5.7(Linux 环境)
- 韩国AI团队抄袭震动学界!1个导师带51个学生,还是抄袭惯犯
猜你喜欢
德国iF多项大奖加冕,这副耳机有多强?音珀GTW 270 Hybrid深度评测
Building blocks for domestic databases, stonedb integrated real-time HTAP database is officially open source!
模板引擎Velocity 基础
Vscode find and replace the data of all files in a folder
【直播预约】数据库OBCP认证全面升级公开课
The Department came to a Post-00 test paper king who took out 25K. The veteran said it was really dry, but it had been
Basic use of MySQL
How to use MySQL language for row and column devices?
Ring iron pronunciation, dynamic and noiseless, strong and brilliant, magic wave hifiair Bluetooth headset evaluation
IM即時通訊開發實現心跳保活遇到的問題
随机推荐
模板引擎Velocity 基礎
免费抽奖 | 《阿巴豆》探索未来系列盲盒数字版权作品全网首发!
Vscode find and replace the data of all files in a folder
Défaillance lors du démarrage de la machine virtuelle VMware: le poste de travail VMware n'est pas compatible avec hyper - V...
What is the digital transformation of manufacturing industry
PR basic clip operation / video export operation
Dataframe gets the number of words in the string
Tutorial on the principle and application of database system (002) -- MySQL installation and configuration: MySQL software uninstallation (Windows Environment)
In the past six months, it has been invested by five "giants", and this intelligent driving "dark horse" is sought after by capital
Mlperf training v2.0 list released, with the same GPU configuration, the performance of Baidu PaddlePaddle ranks first in the world
Principle of motion capture system
毕业季 | 华为专家亲授面试秘诀:如何拿到大厂高薪offer?
Germany if was crowned with many awards. How strong is this pair of headphones? In depth evaluation of yinpo GTW 270 hybrid
Action after deleting laravel's model
How to cancel automatic search and install device drivers for laptops
数据库系统原理与应用教程(003)—— MySQL 安装与配置:手工配置 MySQL(windows 环境)
红队第8篇:盲猜包体对上传漏洞的艰难利用过程
Analysis of PostgreSQL storage structure
Principle of SSM framework
[nodemon] app crashed - waiting for file changes before starting...解决方法