CC

自然万物都趋向从有序变得无序

0%

LightOJ-1173 The Vindictive Coach(DP|计数)

发表于 更新于 分类于 Valine：

题目链接

Problem Description

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 next 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 50.

Input

Input starts with an integer T (T≤ 125), denoting the number of test cases.

Each case contains two positive integers N (1 ≤ N ≤ 50) and m (1 ≤ m ≤ N) separated by a blank space. N represents the number of players in the line-up and m is the captain’s number, who as told is always the first of the line.

Output

For every case, print the case number and the number of possible alignments under the above conditions. Output the result modulo 2^64.

Sample intput

4

3 1

3 3

4 1

7 2

Sample Output

Case 1: 1

Case 2: 1

Case 3: 1

Case 4: 16

题意:

n个不同身高的队员和教练的按照身高排成波浪形……每个人按照身高由低到高编号，其中第m个是教练，他必须在第一个，如果条件允许，排第二的要比m低，如果条件不允许，即其余人都比教练高，则要让差距尽可能小。

思路:

考虑dp

f(i,j)表示前i个数以第j个数开始，并且前两个数的升序的方案数。

g(i,j)表示前i个数以第j个数开始，并且前两个数的降序的方案数。

那么状态转移方程就是：f[i][j]=∑k=ji−1g[i−1][k]f[i][j] = \sum_{k = j}^{i-1}g[i-1][k]

g[i][j]=∑k=1j−1f[i−1][k]g[i][j] = \sum_{k = 1}^{j-1}f[i-1][k]

打表预处理即可。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*************************************************************************
    > File Name: LightOJ-1173.cpp
    > Author: wood
    > Mail: cbcruel@gmail.com
    > Created Time: 2018年08月21日 星期二 08时49分55秒
 ************************************************************************/

#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long LL;
LL f[52][52], g[52][52];

void init(){
    f[1][1] = g[1][1] = 1;
    for(int n = 2; n <= 50; ++n)
        for(int i = 1; i <= n; ++i){
            for(int j = i; j < n; ++j) f[n][i] += g[n-1][j];
            for(int j = 1; j < i; ++j) g[n][i] += f[n-1][j];
        }
}

int main(){
    init();
    int t,kase = 0;
    scanf("%d", &t);
    while(t--){
        int n,m;
        scanf("%d%d", &n,&m);
        LL ans = 0;
        if(m == 1){
            ans = g[n-1][2];
            if(n <= 2) ans = 1;
        }else for(int i = 1; i < m; ++i)
            ans += f[n-1][i];
        printf("Case %d: %llu\n", ++kase, ans);
    }return 0;
}