欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

UVALive - 3516 Exploring Pyramids

程序员文章站 2022-05-21 14:13:37
题意:给你一棵多叉树,每个节点的任意两个子节点都有左右之分,从根节点开始尽量往左走,走不通就回溯,把遇到的字母记录下来,可以得到一个序列,给定一个序列,问有 多少棵树与之相应 思路...

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

多少棵树与之相应

思路:当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 



上一篇: 人数翻倍

下一篇: 女生的两个天敌