lightoj 1173 – The Vindictive Coach（dp）

题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1173

题解：像这种题目显然可以想到n为几时一共有几种排列可以递推出来。然后就是对m的考虑如果m只能在第一位那么显然需要的组合是先下降后上升的如果m不在第一位那么需要的组合是先上升后下降的。于是便可以想到设dp_in[i][j]表示i个数第j个数放在第一个而且是先上升后下降的一共有几种方法，dp_de[i][j]表示i个数第j个数放在第一个而且是先下降后上升的有几种方法。

dp_in[i][j]=sum(dp_de[i-1][j])(i<=j<n)

dp_de[i][j]=sum(dp_in[i-1][j])(1<=j<i)

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef unsigned long long ll;
ll dp_in[][] , dp_de[][];
void init() {
    memset(dp_in ,  , sizeof(dp_in));
    memset(dp_de ,  , sizeof(dp_de));
    dp_in[][] =  , dp_de[][] = ;
    for(int i =  ; i <=  ; i++) {
        for(int j =  ; j <= i ; j++) {
            for(int l =  ; l < j ; l++) {
                dp_de[i][j] += dp_in[i - ][l];
            }
            for(int l = j ; l < i ; l++) {
                dp_in[i][j] += dp_de[i - ][l];
            }
        }
    }
}
int main() {
    int t , Case =  , n , m;
    scanf("%d" , &t);
    init();
    while(t--) {
        scanf("%d%d" , &n , &m);
        ll ans = ;
        if(m == ) {
            if(n <= ) ans += ;
            else ans += dp_de[n - ][];
        }
        else {
            for(int i =  ; i < m ; i++) {
                ans += dp_in[n - ][i];
            }
        }
        printf("Case %d: %llu\n" , ++Case , ans);
    }
    return ;
}