本文共 841 字，大约阅读时间需要 2 分钟。
题意：给出一个字符串。问有多少个满足以下条件的树
从原点开始尽可能左走，不行就回溯，其路径符合给出字符串。
#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;const LL mod = 1000000000;const LL maxn = 300 + 10;LL dp[maxn][maxn];char s[maxn];LL gao(LL i, LL j){ if (~dp[i][j]) return dp[i][j]; if (i == j) return dp[i][j] = 1; if (s[i] != s[j]) return dp[i][j] = 0; LL ans = 0; for (LL x = i + 2; x <= j; x++){ if (s[i] != s[x]) continue; ans += gao(i + 1, x - 1) * gao(x, j); ans %= mod; } return dp[i][j] = ans;}int main(){ while (cin >> s){ LL len = strlen(s); memset(dp, -1, sizeof(dp)); cout << gao(0, len - 1)<
转载于:https://www.cnblogs.com/yigexigua/p/4018407.html