求DP优化
  • 板块学术版
  • 楼主封禁用户
  • 当前回复5
  • 已保存回复5
  • 发布时间2022/8/28 08:08
  • 上次更新2023/10/27 13:22:53
查看原帖
求DP优化
206814
封禁用户楼主2022/8/28 08:08

题目:https://www.luogu.com.cn/problem/U242040

S{C,O,W},s S \subseteq \{C, O, W\} , s为字符串

fi,j=si(i=j)f_{i,j} = s_i (i = j)

fi,j=S{si,sj}(i=j1)f_{i,j} = \complement_S\{s_i,s_j\}(i = j - 1)

fi,j=sj(fi,j=0)f_{i,j} = s_j (f_{i,j}= 0)

fi,j=0(sj=fi,j1)f_{i,j} = 0 (s_j = f_{i,j - 1})

fi,j=Cf_{i,j}=C时成立.

时间复杂度Θ(n(n1))\Theta(n(n - 1)) 有点高

敢问我的DP对吗,应该如何优化

2022/8/28 08:08
加载中...