codeforces dp合集

467C George and Job

题目链接：

https://codeforces.com/problemset/problem/467/C

数据范围：n <= 5000

思路：
这里的dp[i][j]表示到第i个数字的时候用了j对数组的最大值，然后用前缀和预处理一下一段区间的和
dp[i][j] = max(dp[i - 1][j], dp[i - m][j - 1] + sum[i] - sum[i - m])

代码：

https://codeforces.com/contest/467/submission/163677020

446D Increase Sequence

题目链接：
https://codeforces.com/contest/466/problem/D

思路：
用dp来记数，用dp[i]来表示在i这一位的时候的计数状态
先把 a[i] 转化成 h-a[i] ，这样题目就变成了 每次挑一段区间消去1，最后区间变成0 然后可以发现，相邻的两个数相差不能超过1
如果相差为1 $dp[i]=dp[i-1]$
如果相差为0 $dp[i]=dp[i-1]\ast (a[i]+1)$ 这里有两种情况 一种是左边没有左端点 i-1没有右端点 还有一种是i有左端点 i-1有右端点 综合两种情况就可以表示出来
如果相差为-1 $dp[i]=dp[i-1]\ast (a[i-1])$ 右端点可以和前面任意一个左端点进行组合

代码：
https://codeforces.com/contest/466/submission/163799187

463D Gargari and Permutations

题目链接：
https://codeforces.com/contest/463/problem/D

思路：
这道题可以转化为图论，原来是求多个串的最长公共子序列，记一下每个串的每个数出现的位置
然后O(n^2)枚举是否可以每个串的数字 i 都在 每个串的数字 j 前面，如果可以就连一条边
最后从0开始和每个数字连一条边 跑一遍bfs 求从0为起点的一条最长路即可

代码：
https://codeforces.com/contest/463/submission/163987882

461B Appleman and Tree

题目链接：
https://codeforces.com/problemset/problem/461/B
思路：
树上计数，很明显要用树形dp来写，这里要求的数分成的方案数
用dp[i][1/0]来表示i点所在的连通块是否是有颜色
然后考虑状态转移：
dp[x][1]的转移
当前连通块是有色的，和有色的孩子断开 dp[x][1]=dp[x][1]*dp[to][1]
当前连通块是有色的，和没有颜色的孩子连接 dp[x][1]=dp[x][1]*dp[to][1]
当前连通块是无色的，和有色的孩子连接 dp[x][1]=dp[x][0]*dp[to][1]
dp[x][0]的转移
当前联通块是无色的，和有色的孩子断开 dp[x][0]=dp[x][0]*dp[x][1];
当前连通块是无色的，和无色的孩子连接 dp[x][0]=dp[x][0]*dp[x][0];

$dp[x][1]=((dp[to][1]+dp[to][0])\ast dp[x][1]+(dp[to][1]\ast dp[x][0]))$

$dp[x][0]=((dp[to][1]+dp[to][0])\ast dp[x][0])$

代码：
https://codeforces.com/problemset/submission/461/164446403

459E Pashmak and Graph

题目链接：
https://codeforces.com/contest/459/problem/E

思路：

题目要求每条边递增的最长路，可以先按边排序，把边按权值从小到大一条一条的加进来
$dp[x]=max(dp[x],dp[from]+1)$
但是当边的权值相等的时候，dp里面的状态就要同时传递了，我们可以先开一个数组存下来，然后把值赋给dp就好了

代码：
https://codeforces.com/contest/459/submission/164444325

476E Dreamoon and Strings

题目链接：
https://codeforces.com/problemset/problem/476/E

思路：
用 $dp[i][j]$ 来表示在字符串 [ 1 ,i ]里面删掉 j 个字符的最大匹配数量
可以容易得到一个递推式是 $dp[i][j]=max(dp[i][j],dp[i-1][j])$
另一个 利用贪心的想法 当访问到 i 时 从 i 往前找第一个完全能和第二个字符串完全匹配需要被砍掉多少个的数量 这里记这个数量为 x 再注意一下边界 $i-plen-x>=j-x$ 和 $j>=x$
$dp[i][j]=max(dp[i][j],dp[i-plen-x][j-x])$

代码：
https://codeforces.com/contest/476/submission/164898590

479E Riding in a Lift

题目链接：
https://codeforces.com/problemset/problem/479/E

思路：
用 $dp[i][j]$ 来计数，代表 在第i轮的时候，到达第j层的数量是多少，里面的转移 用了一个差分数组，转移的式子很简单

$dp[i][j]=(sum[down]+dp[i-1][j])$
$sum[up+1]=(sum[up+1]-dp[i-1][j])$

再处理一下差分的式子就好了

代码：
https://codeforces.com/contest/479/submission/165296573

478D Red-Green Towers

题目链接：

https://codeforces.com/problemset/problem/478/D

思路：

用 $dp[i][j]$ 来表示到第i层的时候数量为j的方案数量，像01背包一样的状态，进行转移就可以了，因为数组可以能会到1e8 这里直接换上01滚动数组就行
$dp[j]=(dp[j]+dp[j-i])$

统计答案的时候 要把所有满足条件的 $dp[i]$ 全部加上

代码：
https://codeforces.com/contest/478/submission/165305903