UVa 11077 Find the Permutations (计数DP)
The DP Find UVa 计数 Permutations
2023-09-11 14:17:18 时间
题意:给定 n 和 m,问你在 1 ~ n 的所有排列中,有多少个排列满足至少要交换 m 次才能变成 1 2 3 ... n。
析:首先,先考虑一下,某个排列,要变成 1 2 3 .. n,最少要交换几次,这个问题,我们可以把这个排列拆成几个循环,很明显在每个循环中,假设循环长度是 n ,那么至少要交换 n-1 次才能完成,如果不理解的,可以自己举个例子看看,有这个条件,那么就好做了,dp[i][j] 表示 1 ~ i 的排列中至少要交换 j 次才能变成 1 2 3 .. i,dp[i][j] = dp[i-1][j] + (i-1) * dp[i-1][j-1],解释一下这个方程,dp[i-1][j] ,就是直接把 i 放到第 i 个位置,不用交换,正好就是dp[i-1][j],(i-1) * dp[i-1][j-1],这个意思就是对,对于每个排列,我们可以把 i 放到前面的任何循环中,也就是可以把 i 和 前面 1 ~ i-1 上的数进行交换,正好某个循环长度多 1,其他的不变,所以就需要 j 次才能完成。
代码如下:
#pragma comment(linker, "/STACK:1024000000,1024000000") #include <cstdio> #include <string> #include <cstdlib> #include <cmath> #include <iostream> #include <cstring> #include <set> #include <queue> #include <algorithm> #include <vector> #include <map> #include <cctype> #include <cmath> #include <stack> #include <sstream> #include <list> #include <assert.h> #include <bitset> #include <numeric> #define debug() puts("++++") #define gcd(a, b) __gcd(a, b) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define fi first #define se second #define pb push_back #define sqr(x) ((x)*(x)) #define ms(a,b) memset(a, b, sizeof a) #define sz size() #define pu push_up #define pd push_down #define cl clear() #define lowbit(x) -x&x //#define all 1,n,1 #define FOR(i,n,x) for(int i = (x); i < (n); ++i) #define freopenr freopen("in.in", "r", stdin) #define freopenw freopen("out.out", "w", stdout) using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> P; const int INF = 0x3f3f3f3f; const LL LNF = 1e17; const double inf = 1e20; const double PI = acos(-1.0); const double eps = 1e-8; const int maxn = 20 + 10; const int maxm = 1e6 + 2; const LL mod = 1000000007; const int dr[] = {-1, 1, 0, 0, 1, 1, -1, -1}; const int dc[] = {0, 0, 1, -1, 1, -1, 1, -1}; const char *de[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"}; int n, m; const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; inline bool is_in(int r, int c) { return r >= 0 && r < n && c >= 0 && c < m; } LL dp[maxn][maxn]; int main(){ dp[1][0] = 1; for(int i = 2; i < 22; ++i) for(int j = 0; j < i; ++j) dp[i][j] = dp[i-1][j] + (j ? dp[i-1][j-1] * (i-1) : 0); while(scanf("%d %d", &n, &m) == 2 && n + m) printf("%llu\n", dp[n][m]); return 0; }
相关文章
- Understanding the Objective-C Runtime
- hdu1028 Ignatius and the Princess III(递归、DP)
- 【异常】The dependencies of some of the beans in the application context form a cycle
- SQLBackupAndFTP The server principal "NT AUTHORITYSYSTEM" is not able to access the database "xxxx"
- [RxJS 6] The Catch and Rethrow RxJs Error Handling Strategy and the finalize Operator
- [Javascript] Identify the most important words in a document using tf-idf in Natural
- sharepoint2010:The number of items in this list exceeds the list view threshold, which is 20000 items.
- [Typescript] The naked type
- [Vue] Build Vue.js Apps with the Vue-CLI and Nuxt.js
- [Javascript] Manipulate the DOM with the classList API
- AndroidStudio3.0 注解报错Annotation processors must be explicitly declared now. The following dependencies on the compile classpath are found to contain annotation processor.
- 【Codeforces Round #452 (Div. 2) C】 Dividing the numbers
- 【例题 7-9 UVA-1601】The Morning after Halloween
- 【codeforces 767B】The Queue
- 【Codeforces Round #427 (Div. 2) B】The number on the board
- git push报错 fatal: The current branch master has no upstream branch. To push the current
- Android【报错】Description Resource Path Location Type Unparsed aapt error(s)! Cheheck the console for o
- 成功解决bs4__init__.py:181: UserWarning: No parser was explicitly specified, so I'm using the best avai
- HDUOj Ignatius and the Princess III 题目1002
- eclipse git 一个错误:the current branch is not configured for pull No value for key branch.xxx.merge found
- [2013山东ACM]省赛 The number of steps (可能DP,数学期望)
- SVN Error: “' 'x' isn't in the same repository as 'y' ” during merge (并不在同一个版本库中)
- UVA11324-- The Largest Clique(SCC+DP)
- [TroubleShootin]The backup set holds a backup of a database other than the existing 'xxdb' database.
- 【问题解决】The connection to the server localhost:8080 was refused
- 问题解决:The connection to the server xxxxx:6443 was refused - did you specify the right host or port?
- The absolute uri: http://java.sun.com/jsp/jstl/core cannot be resolved in either web.xml or the jar
- MySQL----JDBC无法连接数据库,报The driver has not received any packets from the server的解决办法
- 【2023年4月美赛加赛】Z题:The Future of the Olympics 思路、建模方案、数据来源、相关资料
- Accidental override: The following declarations have the same JVM signature (getWindow()Landroid/vie
- tensorflow报错:Failed to load the native TensorFlow runtime.