金字塔题解报告

ゞ浴缸里的玫瑰 2021-12-19 04:51 208阅读 0赞

[题目传送门][Link 1]

**【题目大意】**

整个金字塔为一个有根树结构，根结点为入口，每个结点涂有一种颜色。机器人从入口开始进行DFS，每经过一个结点，它就会记录这个结点的颜色，最后形成一个序列，求对应这个序列可行的树的结构种类数。

**【思路解析】**

对于序列S，若子串S\[l～r\]对应一棵子树，则S\[l+1\]和S\[r-1\]是进入和离开时产生的。除此之外，\[l,r\]包含的每棵更深的子树都对应着一个子问题，会产生\[l,r\]中的一段，相邻两段之间还有途经树根产生的一个字符。因为\[l,r\]包含的子树个数可能不止两个，如果朴素地枚举子串S\[l～r\]划分点的数量和所有划分点的位置，那么时间复杂度会很高。

那么我们考虑换一种方法，只考虑子串S\[l～r\]的**第一棵子树**是由哪一段构成的。枚举划分点k，令子串S\[l+1～k-1\]构成\[l,r\]的第一棵子树，S\[k～r\]构成\[l,r\]的剩余部分(其他子树)。如果k不同，那么子串S\[l+1～k-1\]代表的子树的大小也不同，所以不可能出现重复计算的结果，并且我们可以得到转移方程(f\[l\]\[r\]表示方案数)：$$if(S\[l\]\\ne S\[r\])\\to f\[l\]\[r\]=0$$

$$if(S\[l\]=S\[r\])\\to f\[l\]\[r\]=f\[l+1\]\[r-1\]+\\sum\_\{l+2\\le k\\le r-2,S\[l\]=S\[k\]\}f\[l+1\]\[k-1\]\*f\[k\]\[r\]$$初始值：$\\forall l\\in \[1,len(S)\],f\[l\]\[l\]=1$，其余均为0。

目标：f\[1\]\[len(S)\]

我们发现，对于方案计数类问题，通常**一个状态的各个决策之间满足“加法原理”**，而**每个决策划分的几个子状态之间满足“乘法原理”**。在设计状态转移方程的决策方式与划分方法时，**一个状态的所有决策之间必须具有互斥性**，才能保证不会重复。

**【代码实现】**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 #define rg register
     3 #define go(i,a,b) for(rg int i=a;i<=b;i++)
     4 #define back(i,a,b) for(rg int i=a;i>=b;i--)
     5 #define ll long long
     6 #define mem(a,b) memset(a,b,sizeof(a))
     7 using namespace std;
     8 const int N=302;
     9 const int mod=1e9;
    10 int f[N][N];
    11 char S[N];
    12 int work(int l,int r){
    13     if(l>r||S[l]!=S[r]) return 0;
    14     if(l==r) return 1;
    15     if(f[l][r]!=-1) return f[l][r];
    16     f[l][r]=0;
    17     go(k,l+2,r)
    18         f[l][r]=(f[l][r]+(ll)work(l+1,k-1)*work(k,r))%mod;
    19     return f[l][r];
    20 }
    21 int main(){
    22     scanf("%s",S);
    23     int n=strlen(S);
    24     mem(f,-1);
    25     printf("%d\n",work(0,n-1));
    26     return 0;
    27 }

代码戳这里

转载于:https://www.cnblogs.com/THWZF/p/11001656.html

[Link 1]: http://contest-hunter.org:83/contest/0x50%E3%80%8C%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E3%80%8D%E4%BE%8B%E9%A2%98/5302%20%E9%87%91%E5%AD%97%E5%A1%94
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211218/3a662366be474e50a7c6dfa11478c6dc.png