ZYB和售货机(图论,环)
个人感觉这道题与基环树没有任何关系,你会发现,每个点最多只有一个入度和出度,所以只能是链或环。
还有就是本题的突破点就在于正确建图,题目的限制保证每个点的入度不大于1,那么我们只需要让每个点连接最优代价的点,这样就可以保证每个点的出度不大于1。
ZYB玩字符串(DP,字符串)
首先我们需要知道字典序不等同于题目中给的排序方法。
然后需要知道的是不能按照顺序只要匹配成功就删掉,这样会不对,比如 \(ababaa\),所以消除的顺序是一个要点。
本题的突破点在于既然不能按顺序来了,那么我们应该会想到区间DP,即 \(f[l][r]\) 表示这段区间是否可行。
但是我们会发现区间长度不一定是模式串的倍数,所以我们规定前缀合法就行。
难点在于转移方程,我们需要想到还有一种可能是先消掉连续的部分,剩下的部分与后面形成一个完整的串。