题解 | 算法竞赛进阶指南 金字塔
金字塔
https://ac.nowcoder.com/acm/contest/1043/C
思路
设为字符串中从
到
部分为一整棵树时的方案数.
我们可以枚举第一棵子树,也就是为一棵子树,其它子树在
为剩余的子树(
与
为根节点,同时也是
的根节点,也就是说这两个点是同一个点).
然后乘法原理与加法原理计算出答案即可.
可以发现,一般情况下,很多状态是无用的.所以用记忆化搜索效率更高.
代码
#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i )
#define fd( i, b, e ) for ( int i(b), I(e); i >= I; --i )
#define go( i, b ) for ( int i(b), v(to[i]); i; v = to[i = nxt[i]] )
template<typename T> inline void cmax( T &x, T y ){ x < y ? x = y : x; }
template<typename T> inline void cmin( T &x, T y ){ y < x ? x = y : x; }
const int MAXN = 305, mod = 1e9;
int N, f[MAXN][MAXN];
char s[MAXN];
int solve( int l, int r ){
if ( l == r ) return 1;
if ( l > r || s[l] != s[r] ) return 0;
if ( f[l][r] >= 0 ) return f[l][r];
f[l][r] = 0;
fp( i, l + 2, r ) if ( s[i] == s[l] )
f[l][r] = ( f[l][r] + 1ll * solve(l + 1, i - 1) * solve(i, r) ) % mod;
return f[l][r];
}
signed main(){
scanf( "%s", s + 1 );
N = strlen( s + 1 ), memset( f, -1, sizeof f );
printf( "%d\n", solve( 1, N ) );
return 0;
} 