题意：
国王的士兵有n个，每个人的身高都不同，国王要将他们排列，必须一高一矮间隔进行，即其中的一个人必须同时高于（或低于）左边和右边。问可能的排列数。例子有1千个，但是最多只算到20个士兵，并且20个的情况的答案已给出。
思路：是此题HDU 4055 Number String(DP计数) 的简单版，所以看此题解就行了。数量较小，可以预先算出来。要同时考虑 <><>和><><这样的两种情况。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
const int N=23;
long long dp1[N][N];
long long dp2[N][N];
long long ans[N];
int j, n;
int cal()
{
ans[1]=1;
dp1[0][1]=dp2[0][1]=1;
for(int i=1; i<N; i++)
{
if(i&1) //大于
{
for(int j=1; j<=i+1; j++)
{
dp1[i][j]=dp1[i][j-1];
dp1[i][j]+=dp1[i-1][j-1];
ans[i+1]+=dp1[i][j];
}
}
else
{
for(int j=i+1; j>0; j--)
{
dp1[i][j]=dp1[i][j+1];
dp1[i][j]+=dp1[i-1][j];
ans[i+1]+=dp1[i][j];
}
}
} for(int i=1; i<N; i++)
{
if(i&1) //大于
{
for(int j=i+1; j>0; j--)
{
dp2[i][j]=dp2[i][j+1];
dp2[i][j]+=dp2[i-1][j];
ans[i+1]+=dp2[i][j];
}
}
else
{
for(int j=1; j<=i+1; j++)
{
dp2[i][j]=dp2[i][j-1];
dp2[i][j]+=dp2[i-1][j-1];
ans[i+1]+=dp2[i][j];
}
}
}
return 0;
}
int main()
{
//freopen("input.txt","r",stdin);
cal();
int p;
cin>>p;
while(p--)
{
scanf("%d%d",&j,&n);
cout<<j<<" "<<ans[n]<<endl;
}
return 0;
}
易理解版本
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
const int N=;
long long dp[N][N],ans[N];
int j, n;
void cal()
{
ans[]=;
for(int k=; k<; k++)
{
dp[][]=;
for(int i=; i<N; i++)
{
if((i+k)&) //大于
{
for(int j=; j<=i+; j++)
{
dp[i][j]=dp[i][j-];
dp[i][j]+=dp[i-][j-];
ans[i+]+=dp[i][j];
}
}
else
{
for(int j=i+; j>; j--)
{
dp[i][j]=dp[i][j+];
dp[i][j]+=dp[i-][j];
ans[i+]+=dp[i][j];
}
}
}
memset(dp,,sizeof(dp) );
}
}
int main()
{
//freopen("input.txt","r",stdin);
cal();
int p;cin>>p;
while(p--)
{
scanf("%d%d",&j,&n);
cout<<j<<" "<<ans[n]<<endl;
}
return ;
}
节省一半空间和代码量的版本
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
const int N=;
long long dp[][N],ans[N];
int j, n;
void cal()
{
ans[]=;
for(int k=; k<; k++)
{
dp[][]=;
for(int i=; i<N; i++)
{
if((i+k)&) //大于
{
for(int j=; j<=i+; j++)
{
dp[i&][j]=dp[i&][j-];
dp[i&][j]+=dp[~i&][j-];
ans[i+]+=dp[i&][j];
}
}
else
{
for(int j=i+; j>; j--)
{
dp[i&][j]=dp[i&][j+];
dp[i&][j]+=dp[~i&][j];
ans[i+]+=dp[i&][j];
}
}
}
memset(dp,,sizeof(dp) );
}
}
int main()
{
//freopen("input.txt","r",stdin);
cal();
int p;cin>>p;
while(p--)
{
scanf("%d%d",&j,&n);
cout<<j<<" "<<ans[n]<<endl;
}
return ;
}
滚动数组版本（更少空间）