- The King's Ups and Downs
- The king has guards of all different heights. Rather than line them up in increasing or decreasing height order, he wants to line them up so each guard is either shorter than the guards next to him or taller than the guards next to him (so the heights go up and down along the line). For example, seven guards of heights 160, 162, 164, 166, 168, 170 and 172 cm. could be arranged as:
or perhaps:
- The king wants to know how many guards he needs so he can have a different up and down order at each changing of the guard for REST of his reign. To be able to do this, he needs to know for a given number of guards, n, how many different up and down orders there are:
- For example, if there are four guards: 1, 2, 3,4 can be arrange as:
- 1324, 2143, 3142, 2314, 3412, 4231, 4132, 2413, 3241, 1423
- For this problem, you will write a program that takes as input a positive integer n, the number of guards and returns the number of up and down orders for n guards of differing heights.
- Input
The first line of input contains a single integer P, (1 <= P <= 1000), which is the number of data sets that follow. Each data set consists of single line of input containing two integers. The first integer, D is the data set number. The second integer, n (1 <= n <= 20), is the number of guards of differing heights.
- Output
- For each data set there is one line of output. It contains the data set number (D) followed by a single space, followed by the number of up and down orders for the n guards.
- Sample Input
- 4
- 1 1
- 2 3
- 3 4
- 4 20
- Sample Output
- 1 1
- 2 4
- 3 10
- 4 740742376475050
题目大意: 给你一组不同身高的士兵, 让你按高低高低高低或低高低高低高的方式排成一排, 并输出这组的排列方式的数目.
解题思想:
当你增加一个数 n 并按题目方式加入前边 n-1 个数之间时, 你可以有 n 个位置插入
1 2 3 4 5 6 7 加入 n=8
0 1 2 3 4 5 6 7 可插 8 八个位置
当我们插入 n 时必须要满足它的前边高 -> 低 - n - 低 -> 高 因为加入的 n 是最大的.
如果我们我们取第 i 个位置插入那么前 i 位置以前共有 i 个数, 那么这 i 个数将有 C[n-1][i], 即从前 n-1 个数中取 i 个数的可能方式数 (排列组合).
记录前边 i 个数中为高低排列的为 dp[i][0], 低高排列的为 [i][1], 由对称性可知两个是相等的且等于 sum[i]/2.
那么可以得到公式
AC 代码:
- #include <iostream>
- #include <cmath>
- using namespace std;
- typedef long long ll;
- ll c[100][100];
- ll dp[25][2];
- ll sum[100];
- void solve(){
- ll t=0;
- dp[0][0]=1;
- dp[0][1]=1;
- dp[1][0]=1;
- dp[1][1]=1;
- for(int i=2;i<=22;i++){
- t=0;
- for(int j=0;j<=i;j++){
- t+=dp[j][0]*dp[i-j-1][1]*c[i-1][j];
- }
- sum[i]=t;
- dp[i][0]=dp[i][1]=t>>1;
- }
- return ;
- }
- int main(){
- ll n,a,b;
- for(int i=0;i<=22;i++){
- c[i][0]=c[i][i]=1;
- }
- c[1][1]=1;
- for(int i=2;i<=22;i++){
- for(int j=1;j<i;j++){
- c[i][j]=c[i-1][j-1]+c[i-1][j];
- }
- }
- sum[0]=0;
- sum[1]=1;
- solve();
- cin>>n;
- while(n--){
- cin>>a>>b;
- cout<<a<<" "<<sum[b]<<endl;
- }
- }
- View Code
来源: https://www.cnblogs.com/meanttobe/p/11267430.html