[BZ1925] [SDOI2010]地精部落
2024-09-05 01:25:41
[BZ1925] [SDOI2010]地精部落
一道很有意思的DP题。
我们发现因为很难考虑每个排列中的数是否使用过,所以我们想到只维护相对关系。
当我们考虑新的一个位置时,给新的位置的数分配一个排名(可以理解为把这个位置的大小插入在原来两个位置的大小的中间)。
所以令\(dp[i][j][0/1]\)表示前i个数,第i个数在前i个数中排名为j,最后两个数是上升/下降时的相对关系的方案数。
那么有:
\[dp[i][j][0]=\sum_{k=1}^{j-1}dp[i-1][k][1]\\
dp[i][j][1]=\sum_{k=j}^{i-1}dp[i-1][k][0]\\
dp[1][1][1]=dp[1][1][0]=1;
\]
dp[i][j][1]=\sum_{k=j}^{i-1}dp[i-1][k][0]\\
dp[1][1][1]=dp[1][1][0]=1;
\]
然后前缀和优化一下:
\[f[i][j][0]=\sum_{k=1}^{j}dp[i][j][0]\\
f[i][j][1]=\sum_{k=1}^{j}dp[i][j][1]\\
\]
f[i][j][1]=\sum_{k=1}^{j}dp[i][j][1]\\
\]
那么转移就是:
\[dp[i][j][0]=f[i-1][j-1][1]\\
dp[i][j][1]=f[i-1][i-1][0]-f[i-1][j-1][0]\\
初始化:f[1][1][0]=f[1][1][1]=1
\]
dp[i][j][1]=f[i-1][i-1][0]-f[i-1][j-1][0]\\
初始化:f[1][1][0]=f[1][1][1]=1
\]
代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
const int maxn=4500;
using namespace std;
int n,p;
int dp[2][maxn][2],f[2][maxn][2];
int main() {
scanf("%d%d",&n,&p);
dp[1][1][0]=dp[1][1][1]=f[1][1][1]=f[1][1][0]=1;
for(int i=2;i<=n;i++) {
int md=i&1;
for(int j=1;j<=i;j++)dp[md][j][0]=dp[md][j][1]=0;
for(int j=1;j<=i;j++) {
dp[md][j][0]+=f[md^1][j-1][1];dp[md][j][0]%=p;
dp[md][j][1]+=f[md^1][i-1][0]-f[md^1][j-1][0];dp[md][j][1]%=p;
}
for(int j=1;j<=i;j++) {
f[md][j][0]=f[md][j-1][0]+dp[md][j][0];f[md][j][0]%=p;
f[md][j][1]=f[md][j-1][1]+dp[md][j][1];f[md][j][1]%=p;
}
}
printf("%d",(((f[n&1][n][1]+f[n&1][n][0])%p)+p)%p);
}
最新文章
- UVA 10089 Repackaging 数学问题
- cookie的设置、获取以及删除
- 嵌入式开发板iTOP-4412开发板移植CAN模块
- 高效的使用STL
- CodeForces 589D Boulevard (数学,相遇)
- Java学习笔记(1)
- POJ 3342 (树形DP)
- Nginx 变量漫谈(七)
- 从零开始Unity3D游戏开发【4 材质球和渲染纹理】
- java使用AES加密解密 AES-128-ECB加密
- javascript遍历select下拉框判断其中值是否与指定值相等
- C#调用winhttp组件 POST登录迅雷
- 前端必备技能之Photosh切图
- .NET作品集:linux下的博客程序
- 使用Bootatrap的心得
- struct导入项目工程时工程旁边出现红色的&#215;号
- 关于SSH的那些事
- BOM模型中常用对象 定义计数器 网页跳转 网页前进后退
- git操作手册
- Mybatis的二级缓存注意点