「神秘的陨石」poj1187 陨石的秘密

神秘的陨石

题目传送门poj1187" role="presentation" style="position: relative;"> $题目传送门 p o j 1187$

题目

陨石的秘密" role="presentation" style="position: relative;"> $陨石的秘密$

TimeLimit:1000MS" role="presentation" style="position: relative;"> $T i m e L i m i t : 1000 M S$

MemoryLimit:10000K" role="presentation" style="position: relative;"> $M e m o r y L i m i t : 10000 K$

TotalSubmissions:2514" role="presentation" style="position: relative;"> $T o t a l S u b m i s s i o n s : 2514$

Accepted:952" role="presentation" style="position: relative;"> $A c c e p t e d : 952$

Description" role="presentation" style="position: relative;"> $D e s c r i p t i o n$

公元11380年，一颗巨大的陨石坠落在南极。于是，灾难降临了，地球上出现了一系列反常的现象。当人们焦急万分的时候，一支中国科学家组成的南极考察队赶到了出事地点。经过一番侦察，科学家们发现陨石上刻有若干行密文，每一行都包含5个整数：

1 1 1 1 6

0 0 6 3 57

8 0 11 3 2845

著名的科学家SS发现，这些密文实际上是一种复杂运算的结果。为了便于大家理解这种运算，他定义了一种SS表达式：

1． SS表达式是仅由’{‘，’}’，’[‘，’]’，’（’，’）’组成的字符串。

2．一个空串是SS表达式。

3．如果A是SS表达式，且A中不含字符’{‘，’}’，’[‘，’]’，则(A)是SS表达式。

4．如果A是SS表达式，且A中不含字符’{‘，’}’，则[A]是SS表达式。

5．如果A是SS表达式，则{A}是SS表达式。

6．如果A和B都是SS表达式，则AB也是SS表达式。

例如

()(())[]

{()[()]}

都是SS表达式。

而

()([])()

[()

不是SS表达式。

一个SS表达式E的深度D(E)定义如下：

例如(){()}[]的深度为2。

密文中的复杂运算是这样进行的：

设密文中每行前4个数依次为L1，L2，L3，D，求出所有深度为D，含有L1对{}，L2对[]，L3对()的SS串的个数，并用这个数对当前的年份11380求余数，这个余数就是密文中每行的第5个数，我们称之为?神秘数?。

密文中某些行的第五个数已经模糊不清，而这些数字正是揭开陨石秘密的钥匙。现在科学家们聘请你来计算这个神秘数。

Input" role="presentation" style="position: relative;"> $I n p u t$

共一行，4个整数L1" role="presentation" style="position: relative;"> $L 1$ ，L2" role="presentation" style="position: relative;"> $L 2$ ，L3" role="presentation" style="position: relative;"> $L 3$ ，D" role="presentation" style="position: relative;"> $D$ 。相邻两个数之间用一个空格分隔。

（0≤L1≤10，0≤L2≤10，0≤L3≤10，0≤D≤30）" role="presentation" style="position: relative;"> $（ 0 \leq L 1 \leq 10 ， 0 \leq L 2 \leq 10 ， 0 \leq L 3 \leq 10 ， 0 \leq D \leq 30 ）$

Output" role="presentation" style="position: relative;"> $O u t p u t$

共一行，包含一个整数，即神秘数。

SampleInput" role="presentation" style="position: relative;"> $S a m p l e I n p u t$

1 1 1 2

SampleOutput" role="presentation" style="position: relative;"> $S a m p l e O u t p u t$

题解

这题显然是个DP。

状态f[a][b][c][d]" role="presentation" style="position: relative;"> $f [a] [b] [c] [d]$ 表示含有a" role="presentation" style="position: relative;"> $a$ 对{}，b" role="presentation" style="position: relative;"> $b$ 对[]，c" role="presentation" style="position: relative;"> $c$ 对()，深度小于等于d" role="presentation" style="position: relative;"> $d$ 的SS串的个数。

有一个直观的转移：套一个括号和两部分合并。

但是这样会有问题：ABC" role="presentation" style="position: relative;"> $A B C$ 这种SS串会由于合并AB，C" role="presentation" style="position: relative;"> $A B ， C$ 和合并A，BC" role="presentation" style="position: relative;"> $A ， B C$ 而重复计数。

所以我们换个转移：(A)B" role="presentation" style="position: relative;"> $(A) B$ ，即枚举一部分套一个括号。这样可以同时处理两种情况，不重不漏。

标程

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iOStream>
#include <algorithm>
using namespace std;

const int P = 11380;
const int M = 35;
const int N = 15;
int f[N][N][N][M];

int fun(int a, int b, int c, int d) {
    if (a + b + c == 0) return 1;
    int tmp = 0;
    for (int i = 0; i < c; i++)
        tmp = (tmp + f[a][b][c - i - 1][d] * f[0][0][i][d - 1]) % P;
    for (int i = 0; i < b; i++)
        for (int j = 0; j <= c; j++)
            tmp = (tmp + f[a][b - i - 1][c - j][d] * f[0][i][j][d - 1]) % P;
    for (int i = 0; i < a; i++)
        for (int j = 0; j <= b; j++)
            for (int k = 0; k <= c; k++)
                tmp = (tmp + f[a - i - 1][b - j][c - k][d] * f[i][j][k][d - 1]) % P;
    return tmp;
}

int main() {
    int l1, l2, l3, d;
    cin >> l1 >> l2 >> l3 >> d;
    f[0][0][0][0] = 1;
    for (int i = 0; i <= l1; i++)
        for (int j = 0; j <= l2; j++)
            for (int k = 0; k <= l3; k++)
                for (int l = 1; l <= d; l++)
                    f[i][j][k][l] = fun(i, j, k, l);
    if (d) f[l1][l2][l3][d] = (f[l1][l2][l3][d] - f[l1][l2][l3][d - 1] + P) % P;
    cout << f[l1][l2][l3][d] << endl;
    return 0;
}

poj1187 陨石的秘密