題目描述

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 arranged 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.

?

輸入

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.

?

輸出

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.

?

樣例輸入

4 1 1 2 3 3 4 4 20

樣例輸出

1 1 2 4 3 10 4 740742376475050

題目鏈接：點(diǎn)擊查看

---

題目大意：給定n個(gè)士兵，身高分別為1~n，各不相同，問(wèn)符合條件的排列有多少種，符合條件的排列為：

奇數(shù)位的士兵全部高于偶數(shù)位的士兵

奇數(shù)位的士兵全部低于偶數(shù)位的士兵

滿足上述兩個(gè)條件的任意一條即視為符合條件

題目分析：這個(gè)題目和之前做過(guò)的一道數(shù)位dp很像，叫Mountain number，也是讓求一定區(qū)間范圍內(nèi)滿足條件的數(shù)字有多少種，那么我們可以借助這個(gè)思想，利用記憶化搜索來(lái)做，因?yàn)槿绻皇菃渭兊谋┝f歸，那么需要遍歷n的階乘的時(shí)間復(fù)雜度，20的階乘就到了1e19的程度了，所以暴力枚舉肯定會(huì)超時(shí)，所以我們選用記憶化搜索，舉個(gè)很簡(jiǎn)單的例子，如果n為4，那么其中的兩種情況為1234和1243，顯而易見(jiàn)，前兩位的12被枚舉了兩次，如果n變大，那么重復(fù)遞歸的時(shí)間復(fù)雜度呈指數(shù)級(jí)別上升，多做了很多無(wú)用的操作，所以我們采取記憶化，類(lèi)似于數(shù)位dp的記憶化，開(kāi)一個(gè)數(shù)組dp[pos][pre][state]，pos代表的是位數(shù)，pre代表的是前面的一個(gè)數(shù)，state代表的是該上升還是該下降，這樣就能將前兩位為12的次數(shù)記下來(lái)，然后在和后面兩位為34和43的相加，這樣需要枚舉的次數(shù)大大降低，就可以再規(guī)定范圍內(nèi)實(shí)現(xiàn)這個(gè)題目了，上代碼：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;int n;LL dp[25][25][2];//pos,prebool vis[25];LL ans=0;LL dfs(int pos,int pre,bool state)//state:0表示該上升，1表示該下降 {if(pos==0)return 1;if(dp[pos][pre][state]!=-1)return dp[pos][pre][state];LL ans=0;for(int i=1;i<=n;i++){if(vis[i])continue;if(state&&pre>i){vis[i]=true;ans+=dfs(pos-1,i,!state);vis[i]=false;}else if(!state&&pre<i){vis[i]=true;ans+=dfs(pos-1,i,!state);vis[i]=false;}}return dp[pos][pre][state]=ans; }int main() { // freopen("input.txt","r",stdin)int w;cin>>w;while(w--){int num;memset(dp,-1,sizeof(dp));cin>>num>>n;if(n==1)//1記得要特判{printf("%d 1\n",num);continue;}memset(vis,false,sizeof(vis));cout<<num<<' '<<dfs(n,-1,0)+dfs(n,25,1)<<endl;}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的中石油训练赛 - The King’s Ups and Downs(记忆化搜索)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。