题解：UVA1362 Exploring Pyramids

· · 题解

考虑欧拉序的性质，一个子树在欧拉序上一定形成一段头尾都相同的区间。

于是考虑区间 DP，定义 dp_{l,r} 表示区间 [l,r] 对应的子树个数。接下来考虑如何在一个区间后拼接一个区间。观察可知，一个子树被拍在欧拉序上后，会被与根节点相同颜色的节点分为若干段，则一个区间 [c,d] 能接到另一个区间 [a,b] 后面的条件就是 b=c 且 S_a=S_b=S_d，转移即可。

但是这样拼接子树会导致同一颗子树被不同的分割方式统计了多次，于是我们考虑强制钦定从后面加进来的区间只能是原区间根节点的一颗子树，而非多颗。也就是做转移的时候转移 dp_{c+1,d-1} 而非 dp_{c,d}。这样计数即可保证不重不漏。

枚举分割点后，判断并利用乘法原理转移即可。时间复杂度 O(n^3)。

注意到一个合法的欧拉序长度只能是奇数，可以在枚举长度的时候跳过偶数，常数能减少一半。

普通递推版本：

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using pi=pair<int,int>;
const int N=305;
const ll mod=1000000000;
char s[N];
int n;
ll dp[N][N];
void solve()
{
    n=strlen(s+1);
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++)dp[i][i]=1;
    for(int len=3;len<=n;len+=2)
    {
        for(int i=1;i+len-1<=n;i++)
        {
            int j=i+len-1;
            for(int k=i;k<j;k++)
            {
                if(s[i]==s[k]&&s[k]==s[j])
                    dp[i][j]=(dp[i][j]+dp[i][k]*dp[k+1][j-1]%mod)%mod;
            }
        }
    }
    cout<<dp[1][n]<<'\n';  
}
int main()
{
    //freopen("sample.in","r",stdin);
    //freopen("sample.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    while(cin>>s+1)solve();
    return 0;
}

记忆化搜索版本：

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using pi=pair<int,int>;
const int N=305;
const ll mod=1000000000;
char s[N];
int n;
ll dp[N][N];
ll dfs(int l,int r)
{
    if(dp[l][r]>=0)return dp[l][r];
    if(r<l||s[l]!=s[r]||(r-l+1)%2==0)return 0;
    if(l==r)return 1;
    dp[l][r]=0;
    for(int i=l;i<r;i++)
    {
        if(s[l]==s[i])
            dp[l][r]=(dp[l][r]+dfs(l,i)*dfs(i+1,r-1)%mod)%mod;
    }
    return dp[l][r];
}
void solve()
{
    n=strlen(s+1);
    memset(dp,-1,sizeof(dp));
    cout<<dfs(1,n)<<'\n';
}
int main()
{
    //freopen("sample.in","r",stdin);
    //freopen("sample.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    while(cin>>s+1)solve();
    return 0;
}