poj 2279(线性 dp)
- 内存爆了
- 将所有新生从高到底排序,
在第i
行插入新生时:
- 人数
<=
该行人数 - 如果在第一行就直接插,不在则 需要满足 ** 该行人数 <= 上一行人数**
f[0][0][0][0][0] = 1
应该为0
,为了不写+1
则初始化为1
;1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36#include <iostream>
#include <string.h>
using namespace std;
int n;
long long f[31][31][31][31][31];
int rows[6];
int main() {
// freopen("a.txt","r",stdin);
while (cin >> n && n) {
memset(f,0,sizeof f);
memset(rows,0,sizeof rows);
for (int i=1; i<=n; ++i) scanf("%d",&rows[i]);
f[0][0][0][0][0] = 1; //边界设置=0也行,每一步多写一次+1就行
for (int i=0; i<=rows[1]; i++)
for (int j=0; j<=rows[2]; j++)
for (int k=0; k<=rows[3]; k++)
for (int a=0; a<=rows[4]; a++)
for (int b=0; b<=rows[5]; b++) {
if ( i+1<=rows[1] )
f[i+1][j][k][a][b] += f[i][j][k][a][b];
if ( j+1<=rows[2] && j+1 <= i) // j+1<=i == j<i ,可以和上一排相等
f[i][j+1][k][a][b] += f[i][j][k][a][b];
if ( k+1<=rows[3] && k+1 <= i && k+1 <= j)
f[i][j][k+1][a][b] += f[i][j][k][a][b];
if ( a+1<=rows[4] && a+1 <= i && a+1 <= j && a+1<=k)
f[i][j][k][a+1][b] += f[i][j][k][a][b];
if ( b+1<=rows[5] && b+1 <= i && b+1 <= j && b+1<=k && b+1<=a)
f[i][j][k][a][b+1] += f[i][j][k][a][b];
}
cout << f[ rows[1] ][ rows[2] ][ rows[3] ][ rows[4] ][ rows[5] ] << endl;
}
return 0;
}
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!