题目大意:n个不同身高的队员和教练的按照身高排成波浪形……
每个人按照身高由低到高编号,
其中第m个是教练,他必须在第一个,
如果条件允许,排第二的要比m低,
如果条件不允许,即其余人都比教练高,则要让差距尽可能小,求排队方案数。
题目思路:
dp_up[i][j],代表i个人排队,第j个人排在队首,且第二个人小于第一个人的方案数
dp-down[i][j],代表i个人排队,第j个人排在队首,且第二个人大于第一个人的方案数
那么dp_up[i][j] = Sum(dp_down[i-1][j]),因为要求第二个人高于第一个人,所以i<j<=n
那么dp_down[i][j] = Sum(dp_up[i-1][j]),1<=j<j。
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define MAXSIZE 505
#define LL unsigned long long using namespace std; LL dp_up[MAXSIZE][MAXSIZE],dp_down[MAXSIZE][MAXSIZE]; LL Solve(int n,int k)
{
if(k==)
{
if(n <= )
return ;
else
return dp_down[n-][];
} LL ans = ;
for(int i=;i<k;i++)
ans += dp_up[n-][i];
return ans;
} int main()
{
memset(dp_up,,sizeof(dp_up));
memset(dp_down,,sizeof(dp_down));
//for(int i=1;i<=50;i++)
dp_up[][] = dp_down[][] = ;
for(int i=;i<=;i++)
{
for(int j=;j<=i;j++)
{
for(int q=;q<j;q++)
{
dp_down[i][j] += dp_up[i-][q];
} for(int q=j;q<=i;q++)
{
dp_up[i][j] += dp_down[i-][q];
}
}
}
int T,n,k,cns=;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
LL ans = Solve(n,k);
printf("Case %d: %llu\n",cns++,ans);
}
return ;
}