MENU

Tags: dp

做题笔记 since 2022.4.4

LG4314 CPU监控

线段树维护历史最值的模版题,要求支持区间加和区间推平,查询区间最大值以及区间历史最大值。

Read More

决策单调性优化 dp 学习笔记

dp 这块的东西又多又杂,本来想把斜率优化或者 wqs 二分一起总结一下,但是难度实在有点大,所以还是按照专题慢慢来。

首先对决策单调性有一个整体的认识。

对于最优化 dp 而言,每个状态从若干个状态转移而来,其中存在一个最优转移点。dp 拥有决策单调性指的就是这个最优转移点按照某种顺序单调变化,例如从左到右等等。

Read More

Solution. CF1336C Kaavi and Magic Spell

Description

给定一个字符串 $S$ 和一个字符串 $T$,每次操作可以删掉 $S$ 的第一个字符,然后放到一个初始为空的字符串 $A$ 的首部或尾部,你可以进行任意次操作,求有多少种不同的方法使得 $T$ 是 $A$ 的前缀。

$|T|\le|S|\le3000$

Read More