poj 2279(线性 dp)

  • 内存爆了
  • 将所有新生从高到底排序,

在第i行插入新生时:

  1. 人数<=该行人数
  2. 如果在第一行就直接插,不在则 需要满足 ** 该行人数 <= 上一行人数**
  • 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 协议 ,转载请注明出处!