动态规划:
dp[a][b][c][d][e]表示第1~5行的人数分别为a,b,c,d,e
dp[a][b][c][d][e] = dp[a - 1][b][c][d][e] + dp[a][b - 1][c][d][e] + dp[a][b][c - 1][d][e] + dp[a][b][c][d - 1][e] + dp[a][b][c][d][e - 1]。限制条件是a > b > c > d > e > 0
#include <iostream>
#include <cstring>
using namespace std;
#define int long long
const int N = 31;
int n, dp[N][N][N][N][N];
signed main() {
while (cin >> n, n) {
memset(dp, 0, sizeof dp);
dp[0][0][0][0][0] = 1;
int s[5] = { 0 };
for (int i = 0; i < n; i++) {
cin >> s[i];
}
for (int a = 0; a <= s[0]; a++) {
for (int b = 0; b <= s[1]; b++) {
for (int c = 0; c <= s[2]; c++) {
for (int d = 0; d <= s[3]; d++) {
for (int e = 0; e <= s[4]; e++) {
int& x = dp[a][b][c][d][e];
if (a && a > b) x += dp[a - 1][b][c][d][e];
if (b && b > c) x += dp[a][b - 1][c][d][e];
if (c && c > d) x += dp[a][b][c - 1][d][e];
if (d && d > e) x += dp[a][b][c][d - 1][e];
if (e) x += dp[a][b][c][d][e - 1];
}
}
}
}
}
cout << dp[s[0]][s[1]][s[2]][s[3]][s[4]] << endl;
}
return 0;
}
暴搜法:(超时)
#include <iostream>
#include <cstring>
using namespace std;
bool st[35];
int n, s, res, g[8][35], lines[8];
void dfs(int x, int y, int u) {
if (u == s) {
res++;
return;
}
if (y == lines[x]) {
y = 0;
x++;
}
for (int i = 1; i <= s; i++) {
if (!st[i]) {
if (x == 0 && y == 0) {
g[x][y] = i;
st[i] = true;
dfs(x, y + 1, u + 1);
st[i] = false;
} else if (x == 0 && y) {
if (i > g[x][y - 1]) {
g[x][y] = i;
st[i] = true;
dfs(x, y + 1, u + 1);
st[i] = false;
}
} else if (x && y == 0) {
if (i > g[x - 1][y]) {
g[x][y] = i;
st[i] = true;
dfs(x, y + 1, u + 1);
st[i] = false;
}
} else if (x && y) {
if (i > g[x][y - 1] && i > g[x - 1][y]) {
g[x][y] = i;
st[i] = true;
dfs(x, y + 1, u + 1);
st[i] = false;
}
}
}
}
}
int main() {
while (cin >> n, n) {
s = res = 0;
memset(st, 0, sizeof st);
for (int i = 0; i < n; i++) {
cin >> lines[i];
s += lines[i];
}
dfs(0, 0, 0);
cout << res << endl;
}
return 0;
}
剪枝法:
#include <iostream>
#include <cstring>
using namespace std;
bool st[35];
int n, s, res, g[8][35], lines[8];
void dfs(int x, int y, int u) {
if (u == s) {
res++;
return;
}
if (y == lines[x]) {
y = 0;
x++;
}
// cnt记录(x, y)的右下方有多少个数
int cnt = -1;
for (int i = x; i < n; i++) {
cnt += lines[i] - y;
}
for (int i = 1; i <= s; i++) {
if (!st[i]) {
if (i > s - cnt) {
continue;
}
if (x == 0 && y == 0) {
g[x][y] = i;
st[i] = true;
dfs(x, y + 1, u + 1);
st[i] = false;
} else if (x == 0 && y) {
if (i > g[x][y - 1]) {
g[x][y] = i;
st[i] = true;
dfs(x, y + 1, u + 1);
st[i] = false;
}
} else if (x && y == 0) {
if (i > g[x - 1][y]) {
g[x][y] = i;
st[i] = true;
dfs(x, y + 1, u + 1);
st[i] = false;
}
} else if (x && y) {
if (i > g[x][y - 1] && i > g[x - 1][y]) {
g[x][y] = i;
st[i] = true;
dfs(x, y + 1, u + 1);
st[i] = false;
}
}
}
}
}
int main() {
while (cin >> n, n) {
s = res = 0;
memset(st, 0, sizeof st);
for (int i = 0; i < n; i++) {
cin >> lines[i];
s += lines[i];
}
dfs(0, 0, 0);
cout << res << endl;
}
return 0;
}