[多校联考2 T3] 排列 (DP)
2024-10-07 13:34:18
DP
Description
对于一个排列,考虑相邻的两个元素,如果后面一个比前面一个大,表示这个位置是上升的,用 I 表示,反之这个位置是下降的,用 D表示。如排列 3,1,2,7,4,6,5 可以表示为 DIIDID。 现在给出一个长度为 n-1的排列表示,问有多少种 1 到n 的排列满足这种表示。
Input
一个字符串 S,S 由 I,D,?组成。?表示这个位置既可以为 I,又可以为 D
对于 20%的数据,S 长度 ≤ 10;
对于 100%的数据,S长度 ≤ 1000。
Output
有多少种排列满足上述字符串。输出排列数模 1000000007。
Sample Input
?D
Sample Output
3
这是一道比较裸的动态规划题目,dp[i][j]表示前 i 位数中,最后一位为第 j 大的方案数。即当转移到i时,前 i - 1 位数是1 ~ i-1 中的数。此时:
- 如果输入为 I,那么 j 可由 1 ~ j-1 转移过来,大于等于 j 的数都加一即可保证前 i 个数为1 ~ i;
- 如果输入为 D,则 j 可由 j ~ i-1 转移而来,同样,大于等于 j 的数字都加一。
- 如果输入为 ?,则将前两种方案加起来。
在实际转移过程中,不用涉及到大于等于 j 的数加一,只需知道转移原理即可。
但是如果直接这样转移当然是不行的,还需注意到,题目中 \(n <= 10^3\),
转移是\(n^3\),会超时。所以我们可以在转移之前维护一个前缀和即可去掉一个\(n\)。使时间复杂度降为\(n^2\)。如果害怕爆空间,还可以采用滚动数组进行优化。
Ps: 本题还有一个点需要注意,由于前缀和取了模,在算下降情况时,可能会出现负数,所以先加上一个mod再取模。
至此,问题完美解决。
代码
#include <cstdio>
int dp[2][1005];
const int mod = 1000000007;
int main() {
dp[0][1] = 1;
int cur = 0;
char x = getchar();
int i = 1;
while(x == 'I'||x == 'D'||x == '?') {
cur ^= 1;i++;
for(int j = 1;j < i;j++)dp[cur^1][j] += dp[cur^1][j-1],dp[cur^1][j] %= mod,dp[cur][j] = 0;
if(x == 'I') {
for(int j = 2;j <= i;j++)dp[cur][j] = dp[cur^1][j-1],dp[cur][j] %= mod;
}
if(x == 'D') {
for(int j = 1;j < i;j++)dp[cur][j] = dp[cur^1][i-1] - dp[cur^1][j-1] + mod,dp[cur][j] %= mod;
}
if(x == '?') {
for(int j = 2;j <= i;j++)dp[cur][j] = dp[cur^1][j-1],dp[cur][j] %= mod;
for(int j = 1;j < i;j++)dp[cur][j] += dp[cur^1][i-1] - dp[cur^1][j-1] + mod,dp[cur][j] %= mod;
}
x = getchar();
}
int ans = 0;
for(int j = 1;j <= i;j++)ans = (ans + dp[cur][j]) % mod;
printf("%d",ans);
return 0;
}
最新文章
- getContentResolver()内容解析者查询联系人、插入联系人
- Android线程池(二)
- 论文阅读之 Inferring Analogous Attributes CVPR 2014
- 单点登录系统构建之二——SSO原理及CAS架构
- Redis 安全
- hdu 4267 树形DP
- linux Page cache和buffer cache----- systemtap
- Ext.Net学习笔记12:Ext.Net GridPanel Filter用法
- Book of Evil
- Linxu安装Lamp环境
- 程序员之---C语言细节22(函数返回指针注意事项&;lt;悬空指针&;gt;、查看进程能够分配的内存大小)
- 【hoj】2651 pie 二分查找
- spring boot 登录注册 demo (二) -- 数据库访问
- The 16th tip of DB Query Analyzer
- Linux基本命令总结(九)
- vue框架与koa2服务器实现跨域通信
- Notepad++远程连接Linux系统
- idea使用docker-maven-plugin插件将项目编译为docker镜像到远程linux服务器 原
- #if _MSC_VER &;gt; 1000 #pragma once #endif 含义
- stylus项目知识点