BZOJ1037 ZJOI2008生日聚会(动态规划)
2024-08-26 06:10:15
设f[i][j][x][y]为安排了i个男孩j个女孩,后缀最大男孩-女孩数为x,最大女孩-男孩数为y的方案数。转移显然。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
#define N 151
#define M 22
#define P 12345678
int n,m,k,f[N][N][M][M];
void inc(int &x,int y){x+=y;if (x>=P) x-=P;}
int main()
{
#ifndef ONLINE_JUDGE
freopen("bzoj1037.in","r",stdin);
freopen("bzoj1037.out","w",stdout);
const char LL[]="%I64d\n";
#else
const char LL[]="%lld\n";
#endif
n=read(),m=read(),k=read();
f[][][][]=;
for (int i=;i<=n+m;i++)
for (int j=max(,i-m);j<=min(n,i);j++)
{
int x=j,y=i-j;
for (int p=;p<=min(k,x);p++)
for (int q=;q<=min(k,y);q++)
{
if (x&&p)
{
inc(f[x][y][p][q],f[x-][y][p-][q+]);
if (q==) inc(f[x][y][p][q],f[x-][y][p-][q]);
}
if (y&&q)
{
inc(f[x][y][p][q],f[x][y-][p+][q-]);
if (p==) inc(f[x][y][p][q],f[x][y-][p][q-]);
}
}
}
int ans=;
for (int i=;i<=k;i++)
for (int j=;j<=k;j++)
inc(ans,f[n][m][i][j]);
cout<<ans;
return ;
}
最新文章
- Action.c(58): Error -27796: Failed to connect to server ";hostname";
- 解决ASP.NET上传文件大小限制
- 访问其他程序的SheardPreferents
- ol新属性
- JSON 之 SuperObject(5): Format 与转义字符
- wp8 在OnBackKeyPress事件中调用MessageBox.Show()崩溃
- sail.js学习 - 一些问题
- Java编程最差代码
- iOS平台基于ffmpeg的视频直播技术揭秘
- Python新手学习基础之数据结构-列表2 添加
- JS/CSS/IMG加载顺序关系之DOMContentLoaded事件
- Matlab图像处理系列1———线性变换和直方图均衡
- WiPlug_百度百科
- 在QLabel上同时显示文字和图片的方法
- Nodejs+MQTT
- 分享12款令人瞠目结舌的WebVR演示和实验效果
- Elasticsearch学习笔记(二)Search API 与 Query DSL
- 【Spring】4、Spring中 @Autowired标签与 @Resource标签 的区别
- 利用TensorFlow实现线性回归模型
- JavaScript函数和内置对象