LG4170/BZOJ1260 「CQOI2007」涂***间DP
区间DP
发现可以转化为区间包含转移。
考虑区间\([l,r]\)，分为两种情况。
\(col[l]=col[r]\)
此时相当于在涂\([l,r-1]\)或\([l+1,r]\)顺带着涂掉
\[f(i,j)=min[f(i+1,j),f(i,j-1)]\]
通常转移
枚举转移点
\[f(i,j)=min[f(i,j),f(i,k)+f(k+1,j)](k \in [i,j))\]
2020-01-04 10:54 已编辑 华中科技大学 计算机类
关注
全部评论
相关推荐
投递科大讯飞等公司7个岗位 > 点赞 评论 收藏
转发
投递韶音科技等公司10个岗位 > 点赞 评论 收藏
转发