1 条题解

  • 0
    @ 2023-10-1 13:59:35

    DFS序列: 从点A出发到B,从点B出发到D,从点D出发返回B,从点B出发到E,从点E出发返回B······从点A出发到C,从点C出发到A。

    从而得到DFS序列:ABDBEBFBACA

    像不像一笔画。

    知道流程后,我们可以发现一个规律,对于每一条边,我们都往返一次,共经历两次,对于n个顶点,我们有n - 1条边,而每一次经过边,都会搜索到一个点,所以DFS序列的长度为1(出发点) + 2 * (n - 1)= 2 * n - 1。

    输入样例:

    ABABABA

    在样例中,DFS序列的长度为7,代入可得顶点的个数为4。

    样例解释:

    状态确立:

    (这里R - 1是不合法的,因为最后一个点是n,R - 1不是一个DFS序列,最多是R - 2)

    我们把一整条DFS序列拆出一个子链,那么这个子链是由红圈中的部分贡献的DFS序列。

    但这些状态不是全部都成立的,合理的状态需要满足一个条件

    K,L,R代表的字母必须相同

    状态转移:

    我们把树分为两部分,总的方案数为两方的方案数之积。

    所以是f[L,R] = f[L,K] * f[K + 1,R]吗?

    我们的方案数是左边的子树 * 右边的子树。

    左边的子树是[L,R],右边的子树是[K + 1,R - 1]。

    所以状态转移:

    f[L,R] = f[L,K] * f[K + 1,R - 1]

    我们最后再把所有不同种树的方案数相加,就得到最后的答案。

    关于区间DP枚举方式的一点介绍:石子合并(算法竞赛进阶指南)_zyc_3的博客-CSDN博客

    代码:

    #include<bits/stdc++.h>
    using namespace std;
    const int mod = 1e9;
    typedef long long ll;
    ll f[305][305];
    string st;
    int n;
     
     
    int main()
    {
    	cin >> st;
    	n = st.size();
    	
    	if(n % 2 == 0){
    		cout << 0;
    	}//判断是否有解
    	else{
    		
    		for(int len = 1;len <= n;len += 2)//len的变化是因为每次子树的点数变化,一个点对应来回两次,对DFS序列贡献为2
    		{
    			for(int l = 0;l + len - 1 < n;l ++)
    			{
    				int r = l + len - 1;
    				if(len == 1)f[l][r] = 1;//初始化
    				else if(st[l] == st[r]){
    					for(int k = l;k < r;k += 2)//k += 2的理由同上 
    					{
    						if(st[k] == st[l])f[l][r] = (f[l][r] + f[l][k] * f[k + 1][r - 1]) % mod;//取不同的k值产生的f[l][r]要求总和
    					}
    				}
    			}
    		}
    		cout << f[0][n - 1];
    	}
    	return 0;
    }
    
    • 1

    信息

    ID
    195
    时间
    1000ms
    内存
    128MiB
    难度
    10
    标签
    递交数
    4
    已通过
    4
    上传者