SP15637题解

Chinshyo

2021-02-21 22:15:07

Solution

# 题意解释 本题要求按规则排列的方案数。那么由题面可知,我们的方案必须要满足以下条件: 1. 每行的人的身高是从左往右减少的。 1. 每列的人的身高是从后向前减少的。 1. 每行的人数是从前往后非减少的。 1. 每行是左对齐的(本程序貌似不用考虑) 注:此题的前后关系是这样的: ``` 后 ### ## # 前 ``` # 解题思路 当时我拿到这道题,首先想到了直接 $dfs$ ,但是这道题有多组数据,所以我们这种解法是不可行的。在这里介绍两种 $DP$的方法。 ## $DP_1$ 本思路参考《算法竞赛进阶指南》P263。由于数据最多5行,我们可以使用 $f[i_1][i_2][i_3][i_4][i_5]$ 来记录方案数, $i_1$ 表示第1行有 $i_1$ 个数, $i_2$ 表示第2行有 $i_2$ 个数,以此类推。在每次找到一种可行的解时,就去看 $f$ 的5个维度在哪个维度插入一个人。那么我们就能很好的得出我们的状态转移方程。若插入在第一维,那么 $f[i_1 + 1][i_2][i_3][i_4][i_5]$ += $f[i_1][i_2][i_3][i_4][i_5]$ ,若插入在第二维,那么 $f[i_1][i_2 + 1][i_3][i_4][i_5]$ += $f[i_1][i_2][i_3][i_4][i_5]$ ,以此类推。本思路我没有写代码,大家可以参考《算法竞赛进阶指南》P263。 ## $DP_2$ 这种思路刚好和 $DP_1$相反,我们反着推。我们同样使用$f[i_1][i_2][i_3][i_4][i_5]$ 来记录方案数,但是我们每次都使用5个 $for$ 循环进行 $dp$。 ### 循环 每一层都枚举每一维可能出现的人的个数。为了保障每行是从前往后减少的,我们需要在结束条件里进行约束。设当前行的人数为 $a_i$ , 那么 $a_i ≤a_{i-1}$ ``` for(a[1] = 0; a[1] <= p[1]; a[1]++) for(a[2] = 0; a[2] <= min(a[1], p[2]); a[2]++) for(a[3] = 0; a[3] <= min(a[2], p[3]); a[3]++) for(a[4] = 0; a[4] <= min(a[3], p[4]); a[4]++) for(a[5] = 0; a[5] <= min(a[4], p[5]); a[5]++) ``` ### 推柿子 一般的,例如在2~4行之间插入,若`a[i] - 1 <= a[i - 1] && a[i] - 1 >= a[i + 1]` ,那么 $f[a_1][a_2][a_3][a_4][a_5] = f[a_1][a_2 - 1][a_3][a_4][a_5] + f[a_1][a_2][a_3][a_4][a_5]$ 本思路要考虑特殊情况。在第1行和第5行插入,会越界。所以我们要特殊处理。 ```cpp switch(i) { case 1://在1行插入 if(a[i] - 1 >= a[i + 1]) f[a[1]][a[2]][a[3]][a[4]][a[5]] = f[a[1] - 1][a[2]][a[3]][a[4]][a[5]] + f[a[1]][a[2]][a[3]][a[4]][a[5]]; break; case 2://在2行插入 if(a[i] - 1 <= a[i - 1] && a[i] - 1 >= a[i + 1]) if(a[2] > 0) f[a[1]][a[2]][a[3]][a[4]][a[5]] = f[a[1]][a[2] - 1][a[3]][a[4]][a[5]] + f[a[1]][a[2]][a[3]][a[4]][a[5]]; break; case 3://在3行插入 if(a[i] - 1 <= a[i - 1] && a[i] - 1 >= a[i + 1]) if(a[3] > 0) f[a[1]][a[2]][a[3]][a[4]][a[5]] = f[a[1]][a[2]][a[3] - 1][a[4]][a[5]] + f[a[1]][a[2]][a[3]][a[4]][a[5]]; break; case 4://在4行插入 if(a[i] - 1 <= a[i - 1] && a[i] - 1 >= a[i + 1]) if(a[4] > 0) f[a[1]][a[2]][a[3]][a[4]][a[5]] = f[a[1]][a[2]][a[3]][a[4] - 1][a[5]] + f[a[1]][a[2]][a[3]][a[4]][a[5]]; break; case 5://在5行插入 if(a[i] - 1 <= a[i - 1]) if(a[5] > 0) f[a[1]][a[2]][a[3]][a[4]][a[5]] = f[a[1]][a[2]][a[3]][a[4]][a[5] - 1] + f[a[1]][a[2]][a[3]][a[4]][a[5]]; break; } ``` # 完整代码 ```cpp #include<bits/stdc++.h> using namespace std; int f[31][31][31][31][31], a[7], p[6]; int main() { int K; while(K != 0) { cin >> K; for(int i = 1; i <= 5; i++) p[i] = 0; for(int i = 1; i <= K; i++) { cin >> p[i];//读入 } for(register int i1 = 0; i1 <= p[1]; i1++) {//赋初值 for(register int i2 = 0; i2 <= p[2]; i2++) { for(register int i3 = 0; i3 <= p[3]; i3++) { for(register int i4 = 0; i4 <= p[4]; i4++) { for(register int i5 = 0; i5 <= p[5]; i5++) { f[i1][i2][i3][i4][i5] = 0; } } } } } for(a[1] = 0; a[1] <= p[1]; a[1]++) { for(a[2] = 0; a[2] <= min(a[1], p[2]); a[2]++) { for(a[3] = 0; a[3] <= min(a[2], p[3]); a[3]++) { for(a[4] = 0; a[4] <= min(a[3], p[4]); a[4]++) { for(a[5] = 0; a[5] <= min(a[4], p[5]); a[5]++) { if(a[1] == 0) { f[a[1]][a[2]][a[3]][a[4]][a[5]] = 1;//起点 } else { for(int i = 1; i <= 5; i++) { switch(i) { case 1: if(a[i] - 1 >= a[i + 1]) f[a[1]][a[2]][a[3]][a[4]][a[5]] = f[a[1] - 1][a[2]][a[3]][a[4]][a[5]] + f[a[1]][a[2]][a[3]][a[4]][a[5]]; break; case 2: if(a[i] - 1 <= a[i - 1] && a[i] - 1 >= a[i + 1]) if(a[2] > 0) f[a[1]][a[2]][a[3]][a[4]][a[5]] = f[a[1]][a[2] - 1][a[3]][a[4]][a[5]] + f[a[1]][a[2]][a[3]][a[4]][a[5]]; break; case 3: if(a[i] - 1 <= a[i - 1] && a[i] - 1 >= a[i + 1]) if(a[3] > 0) f[a[1]][a[2]][a[3]][a[4]][a[5]] = f[a[1]][a[2]][a[3] - 1][a[4]][a[5]] + f[a[1]][a[2]][a[3]][a[4]][a[5]]; break; case 4: if(a[i] - 1 <= a[i - 1] && a[i] - 1 >= a[i + 1]) if(a[4] > 0) f[a[1]][a[2]][a[3]][a[4]][a[5]] = f[a[1]][a[2]][a[3]][a[4] - 1][a[5]] + f[a[1]][a[2]][a[3]][a[4]][a[5]]; break; case 5: if(a[i] - 1 <= a[i - 1]) if(a[5] > 0) f[a[1]][a[2]][a[3]][a[4]][a[5]] = f[a[1]][a[2]][a[3]][a[4]][a[5] - 1] + f[a[1]][a[2]][a[3]][a[4]][a[5]]; break; } } } } } } } } if(K != 0) cout << f[p[1]][p[2]][p[3]][p[4]][p[5]] << endl; } return 0; } ```