SP15637 GNYR04H - Mr Youngs Picture Permutations 解析
分析题目性质
大意就是给 \(k\) 排然后每个数列单调,每个横列单调,求满足这样排列的方案数。
我们发现:与其为每个位置分配某个学生不如考虑将每个学生分给某个位置。
思路
根据以上,不妨设:\(f_{a_1,a_2,a_3,a_4,a_5}\) 分别代表第 \(i\) 排现在人数为 \(a_i\) 的方案数。
那么应该满足以下条件:
- \(a_i < N_i\)
- \(i=1\) 或者 \(a_{i-1}<a_i\)
转移是简单的。
需要注意的是数组。
#include <iostream>
#include <cstdio>
#include <stdlib.h>
#include <algorithm>
#include <cstring>
#include <vector>
#define int long long
using namespace std;
int k,len[35];
signed main(){
for (;~scanf("%lld",&k);) {
if (k == 0) break;
for (int i = 0;i <= 5;i ++) len[i] = 0;
for (int i = 1;i <= k;i ++) scanf("%lld",&len[i]);
vector<vector<vector<vector<vector<int>>>>> f(
len[1] + 1,
vector<vector<vector<vector<int>>>>(
len[2] + 1,
vector<vector<vector<int>>>(
len[3] + 1,
vector<vector<int>>(
len[4] + 1,
vector<int>(
len[5] + 1,
0
)
)
)
)
);
f[0][0][0][0][0] = 1;
for (int a1 = 0;a1 <= len[1];a1 ++)
for (int a2 = 0;a2 <= len[2];a2 ++)
for (int a3 = 0;a3 <= len[3];a3 ++)
for (int a4 = 0;a4 <= len[4];a4 ++)
for (int a5 = 0;a5 <= len[5];a5 ++) {
if (a1 < len[1]) f[a1 + 1][a2][a3][a4][a5] += f[a1][a2][a3][a4][a5];
if (a2 < len[2] && a2 < a1) f[a1][a2 + 1][a3][a4][a5] += f[a1][a2][a3][a4][a5];
if (a3 < len[3] && a3 < a2) f[a1][a2][a3 + 1][a4][a5] += f[a1][a2][a3][a4][a5];
if (a4 < len[4] && a4 < a3) f[a1][a2][a3][a4 + 1][a5] += f[a1][a2][a3][a4][a5];
if (a5 < len[5] && a5 < a4) f[a1][a2][a3][a4][a5 + 1] += f[a1][a2][a3][a4][a5];
}
printf("%lld\n",f[len[1]][len[2]][len[3]][len[4]][len[5]]);
}
return 0;
}
标签:Picture,int,Permutations,Youngs,len,vector,include
From: https://www.cnblogs.com/high-sky/p/18534113