poj[1187][Noi 01]陨石的秘密

Description

公元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

共一行，4个整数L1，L2，L3，D。相邻两个数之间用一个空格分隔。 
（0 <= L1 <= 10，0 <= L2 <= 10，0 <= L3 <= 10，0 <= D <= 30）

Output

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

Sample Input

1 1 1 2

Sample Output

8

题解

字符串dp

将每个字符串表示为四元组(d,a,b,c)，

d->串的深度上限，即该串深度≤d，

a->L1，

b->L2，

c->L3，

计数原理：对于每个当前串A，将其分割为两个串加上任意括号得到的方案数必然为两串的方案数之积。

证明：

举个例子

例如字符串(d,a,b,c)分成了(d,x,y,z)和(d-1,u,v,w)，前者包含了S、R、O的三种实现方案，后者包含了A、E、X、Q的四种实现方案

那么方案数为SASESXSQRARERXRQOAOEOXQ

即3*4种

之后，对于每个字符串(d,a,b,c)，对于深度d的计数可以只考虑(d,x,y,z)和(d-1,u,v,w)（依题意，AB字符串深度为A、B中最大深度）

在此基础上，枚举对该字符串加()[]{}的情况即可。

Rank	Run ID	User	Memory	Time	Language	Code Length	Submit Time

69

16383436

ksq2013

848K

235MS

G++

874B

2016-12-11 17:44:52

程序算跑到比较快的。

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int f[31][11][11][11];
int dp(int d,int a,int b,int c){
    if(!(a|b|c))
        return 1;
    int tmp=0;
    for(int i=0;i<=c-1;i++)
        tmp=(tmp+f[d][a][b][c-i-1]*f[d-1][0][0][i])%11380;
    for(int i=0;i<=b-1;i++)
        for(int j=0;j<=c;j++)
            tmp=(tmp+f[d][a][b-i-1][c-j]*f[d-1][0][i][j])%11380;
    for(int i=0;i<=a-1;i++)
        for(int j=0;j<=b;j++)
            for(int k=0;k<=c;k++)
                tmp=(tmp+f[d][a-i-1][b-j][c-k]*f[d-1][i][j][k])%11380;
    return f[d][a][b][c]=tmp%11380;
}
int main(){
    int l1,l2,l3,dep;
    scanf("%d%d%d%d",&l1,&l2,&l3,&dep);
    f[0][0][0][0]=1;
    for(int d=1;d<=dep;d++)
        for(int a=0;a<=l1;a++)
            for(int b=0;b<=l2;b++)
                for(int c=0;c<=l3;c++)
                    f[d][a][b][c]=dp(d,a,b,c);
    if(dep)
        f[dep][l1][l2][l3]=(f[dep][l1][l2][l3]+11380-f[dep-1][l1][l2][l3])%11380;
    printf("%d
",f[dep][l1][l2][l3]);
    return 0;
}