POJ1187 陨石的秘密 【题解】 线性DP

题面：http://poj.org/problem?id=1187

很自然想到设f[i][j][k][d]为i个小括号，j个中括号，k个大括号，深度小于等于d的解。

那么答案自然就是f[i][j][k][d] - f[i][j][k][d-1] 。

但是最关键的不是在这里，而是如何转移。

我们可以假设加上小于号。

那么自然（res是加上的数）

res=(res+f[a][b][c-i-1][de]*f[0][0][i][de-1])%mod;

那么中括号和大括号一样。

代码如下：

#include<cstdio>
#include<cstdlib>
using namespace std;
const int mod=11380;
int l1,l2,l3,d;
int f[20][20][20][40];
inline int make(int a,int b,int c,int de){
    if (a+b+c==0) return 1;
    int res=0;
    for(int i=0;i<c;i++)
        res=(res+f[a][b][c-i-1][de]*f[0][0][i][de-1])%mod;
    for(int i=0;i<b;i++)
        for(int j=0;j<=c;j++)
            res=(res+f[a][b-i-1][c-j][de]*f[0][i][j][de-1])%mod;
    for(int i=0;i<a;i++)
        for(int j=0;j<=b;j++)
            for(int k=0;k<=c;k++)
                res=(res+f[a-i-1][b-j][c-k][de]*f[i][j][k][de-1])%mod;
    return res;
}
int main()
{
    scanf("%d%d%d%d",&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 z=1;z<=d;z++)
                    f[i][j][k][z]=make(i,j,k,z);
    if(d) f[l1][l2][l3][d]=(f[l1][l2][l3][d]-f[l1][l2][l3][d-1]+mod)%mod;
    printf("%d
",f[l1][l2][l3][d]);
    system("pause");
    return 0;
}