UVALive - 3516 Exploring Pyramids

题意：给你一棵多叉树，每个节点的任意两个子节点都有左右之分，从根节点开始尽量往左走，走不通就回溯，把遇到的字母记录下来，可以得到一个序列，给定一个序列，问有

多少棵树与之相应

思路：当sk=si的时候代表回溯到了树根了，那么分支的序列就是si+1,...sk-1，那么就可以设方案数d(i,j)以及它的分支方案数d(i+1,k-1),可以推出关系d(i,j)=sum{d(i+1.k-1)*d(k,j) ，

i+2

#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 310;
const int mod = 1000000000;
typedef long long ll;

char s[maxn];
int d[maxn][maxn];

int dp(int i,int j){
    if (i == j)
        return 1;
    if (s[i] != s[j])
        return 0;
    int &ans = d[i][j];
    if (ans > 0)
        return ans;
    ans = 0;
    for (int k = i+2; k