写代码三要素：边界、目标、转移
DP要求：无后效性
Mr. Young's Picture Permutations
要求从左到右和从上到下都递减
首先肯定按顺序加入
从左到右很明确，加到最右边
从上到下怎么维护？ 其实就是这一行加完之后不超过上一行就行
发现行数很少，直接变成状态
\(dp[b_1][b_2][b_3][b_4][b_5]\)表示第\(i\)行用了\(b_i\)个位置的方案
初始:\(dp[0][0][0][0][0]=1\)
转移：首先要不超范围，\(b_i<a_i\)
- 第\(1\)行随便加
- 对于第\(i\)行\((i\ne1)\) 要求\(b_i<b_{i-1}\)即可
开始感觉直接枚举是不是会漏因为阶段不是那么好处理，就写了bfs求dag
结果看了一下题解其实是可以直接枚举的，因为对于\(dp[b_1][b_2][b_3][b_4][b_5]\)
他的所有贡献来源其实都是有一维比他小的，在他被枚举到准备更新别人时，其实他已经是求完了
其他两个错误点：
1.unsigned int 直接int不能过 可以用 ll 但注意把所有涉及方案数的int改成ll！！（本题的x）
2. 直接开数组会MLE 因为下面的长度肯定小于上面的，所以第\(i\)行最多\(30/i\)个，节省空间
放一下bfs代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
using namespace std ;
typedef long long ll ;
const int N = 1000010 ;
struct node {
int b1, b2, b3, b4, b5 ;
};
int n ;
int a[10] ;
ll dp[31][31 / 2 + 1][31 / 3 + 1][31 / 4 + 1][31 / 5 + 1] ;
int vis[31][31 / 2 + 1][31 / 3 + 1][31 / 4 + 1][31 / 5 + 1] ;
queue <node> q ;
void init() {
memset(dp, 0, sizeof(dp)) ;
memset(vis, 0, sizeof(vis)) ;
memset(a, 0, sizeof(a)) ;
}
int main() {
while (scanf("%d", &n) != EOF && n) {
init() ;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]) ;
dp[0][0][0][0][0] = 1 ; vis[0][0][0][0][0] = 1 ;
q.push((node){0, 0, 0, 0, 0}) ;
while (!q.empty()) {
node t = q.front() ; q.pop() ;
int b1 = t.b1, b2 = t.b2, b3 = t.b3, b4 = t.b4, b5 = t.b5 ;
ll x = dp[b1][b2][b3][b4][b5] ;
if (b1 < a[1]) {
dp[b1 + 1][b2][b3][b4][b5] += x ;
if (!vis[b1 + 1][b2][b3][b4][b5]) {
q.push((node){b1 + 1, b2, b3, b4, b5}) ;
vis[b1 + 1][b2][b3][b4][b5] = 1 ;
}
}
if (b2 < a[2] && b2 < b1) {
dp[b1][b2 + 1][b3][b4][b5] += x ;
if (!vis[b1][b2 + 1][b3][b4][b5]) {
q.push((node){b1, b2 + 1, b3, b4, b5}) ;
vis[b1][b2 + 1][b3][b4][b5] = 1 ;
}
}
if (b3 < a[3] && b3 < b2) {
dp[b1][b2][b3 + 1][b4][b5] += x ;
if (!vis[b1][b2][b3 + 1][b4][b5]) {
q.push((node){b1, b2, b3 + 1, b4, b5}) ;
vis[b1][b2][b3 + 1][b4][b5] = 1 ;
}
}
if (b4 < a[4] && b4 < b3) {
dp[b1][b2][b3][b4 + 1][b5] += x ;
if (!vis[b1][b2][b3][b4 + 1][b5]) {
q.push((node){b1, b2, b3, b4 + 1, b5}) ;
vis[b1][b2][b3][b4 + 1][b5] = 1 ;
}
}
if (b5 < a[5] && b5 < b4) {
dp[b1][b2][b3][b4][b5 + 1] += x ;
if (!vis[b1][b2][b3][b4][b5 + 1]) {
q.push((node){b1, b2, b3, b4, b5 + 1}) ;
vis[b1][b2][b3][b4][b5 + 1] = 1 ;
}
}
}
printf("%lld\n", dp[a[1]][a[2]][a[3]][a[4]][a[5]]) ;
}
}