The Vindictive Coach

The coach of a football team, after suffering for years the adverse comments of the media about his tactics, decides to take his revenge by presenting his players in a line-up in such a way that the TV cameras would be compelled to zigzag in a ridiculous bobbing motion, by alternating taller and shorter players. However, the team captain objects that he must be the first of the line by protocolary reasons,and that he wants to be seen in the best possible light: that is, he should not have a taller colleague nest to him unless there is no alternative (everyone else is taller than him). Even in this case, the height difference should be as small as possible, while maintaining the zigzag arrangement of the line.

With this condition the coach addresses an expert in computation (i.e. you) to help him find the number of different alignments he may make, knowing that all players have a different height. They are always numbered by stature starting by 1 as the shortest one. Of course the number of players may be arbitrary, provided it does not exceed 22.

Input 

It is a set of lines, each of which contains two positive integers N and m separated by a blank space. represents the number of players in the line-up and m the captain's number, who as told is always the first of the line.

Output 

For every line of the input a line with positive integer indicating the number of possible alignments under the above conditions.

Sample Input 

3 1
3 3
4 1

Sample Output 

1
1
1

---

Miguel A. Revilla
2000-02-09

題目描述：

n 個人，身高從 1 到 n 由低到高編號，他們現在被要求排成一排。

如果隊長(排在第一個)不是最矮的情況，希望排成高矮高矮 ... 的之之型。

反之是最矮的話，則希望第二個人的高度越小越好(同時也就是跟隊長高度差越小)。

問總共有幾種排法。

題目解法：

dp[i][j][k] 表示 i 個人，第一個人高度 j，k 表示再 j 之後，是比 j 高還是比 j 矮。
(即隊長 j, 接下來是高矮高矮還是矮高矮高)

則 dp[i][j][0] += dp[i-1][k][1]; // k >= j, k <= i
在隊長為 j 的高矮高矮中，由之前 i-1 個人身高為 k 開頭的接，
相當於將一個身高 j 放到所有排列方法的頭，而原本比他高的人身高就全部往後推移增加。

反之求矮高矮高
              dp[i][j][1] += dp[i-1][k][0];// 1 <= k < j

最後輸出要特別處理。

當 1 號當隊長時，如果 n > 2，則一定是 3 號接著，反之 2 號接著。

#include <stdio.h>
long long dp[30][30][2];
//dp[i][j][k], using 1...i, {j, ...}, k:0 up, 1 down for j
int main() {
    int n, m;
    int i, j, k;
    dp[1][1][0] = 1;
    dp[1][1][1] = 1;
    for(i = 2; i < 30; i++) {
        for(j = 1; j <= i; j++) {
            for(k = j; k <= i; k++)//{j up,{k down, ...}}
                dp[i][j][0] += dp[i-1][k][1];
            for(k = 1; k < j; k++)
                dp[i][j][1] += dp[i-1][k][0];
        }
    }
    while(scanf("%d %d", &n, &m) == 2) {
        long long ret = 0;
        if(m > 1) {// not shortest first.
            for(i = 1; i < m; i++) {// + {m, i, ...}
                ret += dp[n-1][i][0];
            }
        } else {
            if(n == 1 || n == 2)
                ret = 1;
            else
                ret = dp[n-1][2][1];//{1, 3, ...}
        }
        printf("%lld\n", ret);
    }
    return 0;
}