[Gym 101334E]Exploring Pyramids(区间dp)

题意：给定一个先序遍历序列，问符合条件的树的种类数

解题关键：枚举分割点进行dp，若符合条件一定为回文序列，可分治做，采用记忆化搜索的方法。

转移方程：$dp[i][j] = \sum {dp[i + 1][k - 1]*dp[k][j]} $ 令$dp[i][j]$表示i到j里数量

1、记忆化搜索

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod=1e9;

ll dp[][];

char a[];  

ll dfs(int l,int r){

    if(dp[l][r]!=-)return dp[l][r];

    if(l==r) return dp[l][r]=;

    if(a[l]!=a[r]) return ;

    dp[l][r]=;

    for(int i=l+;i<=r;i+=){

        if(a[i]==a[l]){

            dp[l][r]+=dfs(l+,i-)*dfs(i,r);//一定注意dp的顺序

            dp[l][r]%=mod;

        }

    }

    return dp[l][r];

}

int main(){

    freopen("exploring.in", "r", stdin);

    freopen("exploring.out", "w", stdout);

    while(~scanf("%s", a)){

        memset(dp,-,sizeof dp);

        int len=strlen(a);

        printf("%lld\n", dfs(,len-)%mod);

        }

    return ;

}

2、区间dp

#include<bits/stdc++.h>

#define mod 1000000000

using namespace std;

typedef long long ll;

string a;

ll dp[][],len;

int main(){

    freopen("exploring.in", "r", stdin);

    freopen("exploring.out", "w", stdout);

    while(cin>>a){

        memset(dp,,sizeof dp);

        len=a.size();

        if(len%==){

            cout<<<<endl;

            continue;

        }

        for(int i=;i<len;i++)    dp[i][i]=;

        for(int i=;i<len;i+=){

            for(int l=,r;l+i<len;l++){

                r=l+i;

                if(a[l]==a[r]){

                    for(int k=l+;k<=r;k++)

                        if(a[k]==a[l])

                            dp[l][r]=(dp[l][r]+dp[l+][k-]*dp[k][r])%mod;

                }

            }

        }

        cout<<dp[][len-]<<endl;

    }

    return ;

}

巴特西

[Gym 101334E]Exploring Pyramids(区间dp)

最新文章

热门文章