HDU 4489 The King’s Ups and Downs (DP+数学计数)
The and HDU 数学 DP 计数 UPS
2023-09-11 14:17:18 时间
题意:给你n个身高高低不同的士兵。问你把他们按照波浪状排列(高低高或低高低)有多少方法数。
析:这是一个DP题是很明显的,因为你暴力的话,一定会超时,应该在第15个时,就过不去了,所以这是一个DP计数问题。
那么我们应该怎么想呢,我们先假设前 i-1 个已经放好了,然后第 i 个一定是最高的,所以,他一定要在前面找一个低后面放上他,肯定不能放在高的后面,
那么状态就有的表示了,d[i][0]表示是以低结尾,d[i][1]是以高结尾,我们假设放第 i 个士兵时,前面有 j 个,那么后面就有 i - j - 1个,前面的乘以后面的,
再乘以 C[i-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 <stack> using namespace std; typedef long long LL; typedef pair<int, int> P; const int INF = 0x3f3f3f3f; const double inf = 0x3f3f3f3f3f3f; const LL LNF = 100000000000000000; const double PI = acos(-1.0); const double eps = 1e-8; const int maxn = 1e2 + 5; const int mod = 1e9 + 7; const char *mark = "+-*"; const int dr[] = {-1, 0, 1, 0}; const int dc[] = {0, 1, 0, -1}; int n, m; inline bool is_in(int r, int c){ return r >= 0 && r < n && c >= 0 && c < m; } inline LL Max(LL a, LL b){ return a < b ? b : a; } inline LL Min(LL a, LL b){ return a > b ? b : a; } inline int Max(int a, int b){ return a < b ? b : a; } inline int Min(int a, int b){ return a > b ? b : a; } LL C[25][25]; LL d[25]; void init(){ for(int i = 0; i < 25; ++i) C[i][0] = 1; for(int i = 1; i < 22; ++i) for(int j = 1; j <= i; ++j) C[i][j] = C[i-1][j] + C[i-1][j-1]; d[0] = d[1] = 1; for(int i = 2; i < 21; ++i){ LL ans = 0; for(int j = 0; j <= i; ++j) ans += d[j] * d[i-j-1] * C[i-1][j]; d[i] = ans/2; } } int main(){ init(); int T; cin >> T; while(T--){ scanf("%d %d", &m, &n); printf("%d ", m); if(1 == n) printf("1\n"); else printf("%I64d\n", d[n]<<1); } return 0; }
相关文章
- The three top-paying tech roles in 2022 and the skills you need to land them
- What is the difference between AntiXss.HtmlEncode and HttpUtility.HtmlEncode?
- What is the difference between application server and web server?
- What is the difference between UserControl, WebControl, RenderedControl and CompositeControl?
- Can't bind multiple parameters ('header' and 'parameters') to the request's content.
- git删除本地和远程文件,解决 fatal: Not a git repository (or any of the parent directories): .git 问题
- 报错:The specified datastore driver ("com.mysql.jdbc.Driver") was not found in the CLASSPATH. Please check your CLASSPATH specification, and the name of the driver.
- No supported encrypter found. The cipher and / or key length are invalid.
- Understanding the Router
- BZOJ1991 : Pku2422 The Wolves and the Sheep
- TOJ 3517 The longest athletic track
- xtu read problem training 3 A - The Child and Homework
- OpenCV 程序报错 The application has requested the Runtime to terminate it in an unusual way.
- HDU 5443 The Water Problem (水题,暴力)
- CodeForces 682C Alyona and the Tree (树上DFS)
- UVa 1153 Keep the Customer Satisfied (贪心+优先队列)
- The promises and challenges of std::async task-based parallelism in C++11 C++11 std::async/future/promise
- Failed to load module “canberra-gtk-module“ 或 Using GTK+ 2.x and GTK+ 3 in the same process is not
- CF 439C(251C题)Devu and Partitioning of the Array
- iOS ERROR: unable to get the receiver data from the DB 解决方式
- [daily paper 4]2023 03 02 2019 65 CASpMV A Customized and Accelerative SpMV Framework for the Sunway
- 【Android】The application has stopped unexpectedly.Please try again.
- [LeetCode] Find the Derangement of An Array 找数组的错排
- The current request is not a multipart request异常
- The type name 'IComponentConnector' could not be found in the namespace 'System.Windows.Markup'