POJ2279 Mr Young's Picture Permutations[动态规划]

$Mr.Youn{g}^{\prime }s Picture Permutations$Mr.Young′s　Picture　Permutations

题目描述

链接

Solution

根据其要求的单调性, 可以按从高到矮, 从左向右, 从上向下放人, 这样既即可保证都为合法
因为数据很小, 所以可以将每行状态保存在 $dp\left[a_1\right]\left[a_2\right]\left[a_3\right]\left[a_4\right]\left[a_5\right]$dp[a1​][a2​][a3​][a4​][a5​]中,
枚举每个状态进行转移
转移: 若要在第 $i$i行放一个人, 则需满足该行人数小于规定人数, 小于上一行人数(除了第一行)
起点: $dp\left[0\right]\left[0\right]\left[0\right]\left[0\right]\left[0\right]=1$dp[0][0][0][0][0]=1
终点: $dp\left[N_1\right]\left[N_2\right]\left[N_3\right]\left[N_4\right]\left[N_5\right]$dp[N1​][N2​][N3​][N4​][N5​]
时间复杂度: $O\left(N^5\right)$O(N5)
空间复杂度: $O\left(N^5\right)$O(N5)

Code

#include<cstdio>
#include<cctype>
#include<cstring>

#define reg register

int read(){
        int s = 0, flag = 1;
        char c;
        while((c=getchar()) && !isdigit(c))
                if(c == '-'){ flag = -1, c = getchar(); break ; }
        while(isdigit(c)) s = s*10 + c-'0', c = getchar();
        return s * flag;
}

int K;
int n[6];

void Work(){
        memset(n, 0, sizeof (n));
        for(reg int i = 1; i <= K; i ++) n[i] = read();
        long long dp[n[1]+1][n[2]+1][n[3]+1][n[4]+1][n[5]+1];
        memset(dp, 0, sizeof(dp));
        dp[0][0][0][0][0] = 1;
        for(reg int a1 = 0; a1 <= n[1]; a1 ++)
                for(reg int a2 = 0; a2 <= n[2]; a2 ++)
                        for(reg int a3 = 0; a3 <= n[3]; a3 ++)
                                for(reg int a4 = 0; a4 <= n[4]; a4 ++)
                                        for(reg int a5 = 0; a5 <= n[5]; a5 ++){
                                                if(a1 < n[1]) dp[a1+1][a2][a3][a4][a5] += dp[a1][a2][a3][a4][a5];
                                                if(a2 < n[2] && a2 < a1) dp[a1][a2+1][a3][a4][a5] += dp[a1][a2][a3][a4][a5];
                                                if(a3 < n[3] && a3 < a2) dp[a1][a2][a3+1][a4][a5] += dp[a1][a2][a3][a4][a5];
                                                if(a4 < n[4] && a4 < a3) dp[a1][a2][a3][a4+1][a5] += dp[a1][a2][a3][a4][a5];
                                                if(a5 < n[5] && a5 < a4) dp[a1][a2][a3][a4][a5+1] += dp[a1][a2][a3][a4][a5];
                                        }
        printf("%lld\n", dp[n[1]][n[2]][n[3]][n[4]][n[5]]);
}

int main(){
        while(K = read()) Work();
        return 0;
}