[BZOJ 1055][HAOI2008]玩具取名(DP)

时间:2021-10-02 03:18:59

题目:http://www.lydsy.com:808/JudgeOnline/problem.php?id=1055

分析:

比较难想的dp

f[i][j][c]表示i..j能否压缩成字符c

那么怎么转移呢

如果存在i<=k<j,f[i][k][c1]=true且f[k+1][j][c2]=true且c1c2可以压缩成字符c(这个根据读入判断),那么f[i][j][c]就是true。

记忆化搜索比较好实现了。