HDU4689Derangement (动态规划)
规划 动态
2023-09-14 09:08:58 时间
题目链接:传送门
题意:
对于一个由1~n组成的长度为n的序列来说它有n!种排法。我们定义初始的排列为1,2,3,...,n对于兴许的排列假设a[i]>i则用'+'表示。a[i]<i用'-'表示,给定一个长度为n的由'+'与'-'组成的字符串,问满足这个条件的排列有多少种。
分析:
设dp[i][j]表示前i个字符中有j个'+'没有排,'-'排完了的方案数。
那么我们能够依据字符的正负分成两种情况来考虑。
1.a[i]='+':那么一种情况就是前面有j-1个加号没有放,并且这个加号也不放。或者前面已经有j个加号没有放。那么我们这个加号假设也不放的话就要把这个数放在前面j个加号没有放的位置上,有j种可能。
因此这时dp[i][j]=dp[i-1][j-1]+dp[i-1][j]*j.
2.a[i]='-':相同的一种情况就是前面已经有j+1个加号,我们须要把前面这个数放在前面的加号没有放的位置,又要从前面加号没有放的位置选一个放在这个位置一共j*j种方案。另一种是假设前面有j个加号没有放的话我们就仅仅须要从这j个数种选一个放在这个位置上就可以。,因此此时dp[i][j]=dp[i-1][j+1]*j*j+dp[i-1][j]*j;
代码例如以下:
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int maxn = 30; typedef long long LL; LL dp[maxn][maxn]; char s[maxn]; int main() { while(~scanf("%s",s)){ int len = strlen(s); memset(dp,0,sizeof(dp)); dp[0][0]=1LL; for(int i=1;i<=len;i++){ if(s[i-1]=='+'){ for(int j=1;j<=len;j++){ dp[i][j]+=dp[i-1][j-1]; dp[i][j]+=dp[i-1][j]*(LL)j; } } if(s[i-1]=='-'){ for(int j=1;j<=len;j++){ dp[i][j-1]+=dp[i-1][j]*(LL)j*j; dp[i][j]+=dp[i-1][j]*(LL)j; } } } printf("%I64d\n",dp[len][0]); } return 0; }
相关文章
- 制定待办事项清单,有效规划工作和生活
- 机器人运动规划中的构形空间(Configuration Space)
- MoveIt运动规划-1
- Java实现 LeetCode 1162 地图分析(可以暴力或者动态规划的BFS)
- Java实现 LeetCode 552 学生出勤记录 II(数学转换?还是动态规划?)
- Java动态规划实现最短路径问题
- 2015闲聊、总结、规划、人生
- 动态规划题目汇总
- 数据结构和算法—动态规划
- 电子商务平台:云上高可用解决方案、优化、及未来规划
- LeetCode-828. 统计子串中的唯一字符【哈希表,字符串,动态规划】
- Leetcode学习计划之动态规划入门day18(300,376)
- Leetcode学习计划之动态规划入门day10(413,91)
- Leetcode213: 打家劫舍 II(medium, 动态规划)
- Atitit 我们的devops战略与规划 规范 推荐标准
- 【 【henuacm2016级暑期训练】动态规划专题 G】 Palindrome pairs
- 基于Dijkstra和A*算法的机器人路径规划(Matlab代码实现)
- 基于蚁群算法的时延Petri网(ACOTPN)路径规划算法(Matlab代码实现)
- 基于多级适应方法的无人机(UAV)在发动机输出情况下的导航和路径规划(Matlab代码实现)
- 聊聊不太符合常规思维的动态规划算法
- 全面拥抱 FastApi — 多应用程序项目结构规划
- 最低票价-c语言动态规划
- [LeetCode] 516. 最长回文子序列 ☆☆☆(动态规划)
- [LeetCode] 337. 打家劫舍III ☆☆☆(动态规划)
- [LeetCode] 647. 回文子串 ☆☆☆(最长子串、动态规划、中心扩展算法)
- [LeetCode] 213. 打家劫舍II ☆☆☆(动态规划)
- 机器人C++库(11)Robotics Library 之指定路径规划算法
- 一文搞懂动态规划,上机考试再也不会慌
- 动态规划03---你的背包怎么背也背不烂~~~专治各种完全背包问题