codeforces DP专题小结


  1. 间隔选择类：当选择了a[i]后，不能选择a[i-1]或/和a[i+1]。

    可以思考就a[i]选择/未选择两种情况，进行动态规划。

    dp[i]=max(dp[i-1](a[i-1] is chosen),dp[i-2]+a[i](a[i] is not chosen))

    ：

    A. Boredom


  2. 满足条件类：至少选择某一条件（如最小值大于等），最多某一不符合等

    是否操作类：做多可以操作一次（翻转、改值等）

    dp[i][1]表示已满足或已消耗或已操作，dp[i][0]表示未满足或未消耗或未消耗

    ：

    C. k-Tree

    C. Hard problem


  3. 范围选择类：当选择了a[i]后，不能在a[i]左或/和右范围dis[i]内选择。

    dp[i]=dp[i-dis[i]-1]+1

    ：

    A. Chain Reaction


  4. 范围选择类：当选择了a[i]后，必须选择包含a[i]且长为的连续序列

    ：

    D. Flowers


  5. 序列选择个长度为的子序列，其累积和最大。

    ，考虑在选取个时累计和最大值

    ：

    C. George and Job

相关专题：区间


  1. 条件累计类：在一个序列中选择k个满足条件的元素，有多少种方法

    区间前缀和思想，表示共有个满足元素条件下的数量总和

    ：

    C. Another Problem on Strings


  2. 次数矩阵范围累计类：在二维空间内某一区域的统计，多与离线处理在线查询有关

    ：

    C. Star sky


  3. 等和平分类：将一个序列平分为个和相等（为）的的序列，有多少种方法。

    ：

    C. Number of Ways


  4. 修改序列中的一个数，使得该序列的最长上升子序列最长。

    ：

    A. DZY Loves Sequences

专题

1 树状dp

D. Serval and Rooted Tree

一个给定构造的有根树，其结点有两种，返回子节点的最大值，返回子节点的最小值，共有个叶子节点如何给它们赋初值，使得根节点的数值最大。

分类讨论如下：

  1. 叶子节点：

  2. 结点：

  3. 结点：

最终

此处是结点出最少花费的降序叶子节点。

专题

1 字符串DP

H. Subsequences (hard version)

给定一个长度为n()的字符串，将其任意的子序列放入集合S中，S中元素不能重复，每次放入的花费是n-t，t为子序列长度，求使S中元素个数达到k的最小花费是多少，若无法达到k个则输出-1。

类比：

L3-020 至多删三个字符 (30 分)

给定一个由小写字母组成的字符串（长度为[4,106]），允许至多删除其中3个字符，结果可能有多少种不同的字符串？

如输入ababcc输出为25

删掉 0 个字符得到 "ababcc"。

删掉 1 个字符得到 "babcc", "aabcc", "abbcc", "abacc" 和 "ababc"。

删掉 2 个字符得到 "abcc", "bbcc", "bacc", "babc", "aacc", "aabc", "abbc", "abac" 和 "abab"。

删掉 3 个字符得到 "abc", "bcc", "acc", "bbc", "bac", "bab", "aac", "aab", "abb" 和 "aba"。

令表示前i个删除了j个字母的字符串种类数，若没有出现一样的话，。

但如出现相同的呢？如"ababcc"前6个删除1个时，删除第五个和删除第六个是同一种情况。

因此，对于这种形式的，我们把第一个x之前出现过的种数去掉即可，注意只向前找到第一个相同的即可，如果前面还有，但他已经被处理过了。