Codeworks DP collection

467C George and Job

Topic link ：

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

Data range ：n <= 5000

Ideas ：
there dp[i][j] To i A number is used j For the maximum value of the array , Then use prefix and preprocess the sum of an interval
dp[i][j] = max(dp[i - 1][j], dp[i - m][j - 1] + sum[i] - sum[i - m])

Code ：

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

446D Increase Sequence

Topic link ：
https://codeforces.com/contest/466/problem/D

Ideas ：
use dp To count , use dp[i] To show that in i The counting state of this bit
The first a[i] Turn it into h-a[i] , So the title becomes Pick a section to eliminate each time 1, Finally, the interval becomes 0 And then you can see that , The difference between two adjacent numbers cannot exceed 1
If the difference is 1 $dp[i]=dp[i-1]$
If the difference is 0 $dp[i]=dp[i-1]\ast (a[i]+1)$ There are two situations here One is that there is no left endpoint on the left i-1 There is no right endpoint The other is i With left endpoint i-1 There is a right endpoint It can be expressed by combining the two situations
If the difference is -1 $dp[i]=dp[i-1]\ast (a[i-1])$ The right endpoint can be combined with any previous left endpoint

Code ：
https://codeforces.com/contest/466/submission/163799187

463D Gargari and Permutations

Topic link ：
https://codeforces.com/contest/463/problem/D

Ideas ：
This problem can be transformed into graph theory , It turns out that the longest common subsequence of multiple strings , Note the position of each number in each string
then O(n^2) Enumerate whether the number of each string i All in The number of each string j front , If you can connect one side
Finally from the 0 Start with one side of each number Run it over bfs Seek from 0 The longest way to start

Code ：
https://codeforces.com/contest/463/submission/163987882

461B Appleman and Tree

Topic link ：
https://codeforces.com/problemset/problem/461/B
Ideas ：
Count on tree , It's obvious to use a tree dp To write , The number of schemes required here
use dp[i][1/0] To express i Whether the connected block where the point is located has color
Then consider state transition ：
dp[x][1] The transfer of
Currently connected blocks are colored , Disconnect from colored children dp[x][1]=dp[x][1]*dp[to][1]
Currently connected blocks are colored , Connect with children without color dp[x][1]=dp[x][1]*dp[to][1]
The current connected block is colorless , Connect with colored children dp[x][1]=dp[x][0]*dp[to][1]
dp[x][0] The transfer of
The current connection block is colorless , Disconnect from colored children dp[x][0]=dp[x][0]*dp[x][1];
The current connected block is colorless , Connect with colorless children 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])$

Code ：
https://codeforces.com/problemset/submission/461/164446403

459E Pashmak and Graph

Topic link ：
https://codeforces.com/contest/459/problem/E

Ideas ：

The question requires the longest way for each side to increase , You can sort by edge first , Add the edges one by one according to the weight from small to large
$dp[x]=max(dp[x],dp[from]+1)$
But when the weights of the edges are equal ,dp The state inside will be transferred at the same time , We can open an array and save it , Then assign the value to dp Just fine

Code ：
https://codeforces.com/contest/459/submission/164444325

476E Dreamoon and Strings

Topic link ：
https://codeforces.com/problemset/problem/476/E

Ideas ：
use $dp[i][j]$ To represent in string [ 1 ,i ] Delete the inside j The maximum matching number of characters
It is easy to get a recursive formula is $dp[i][j]=max(dp[i][j],dp[i-1][j])$
the other one Use greedy ideas When access to the i when from i Go ahead and find out how many numbers need to be cut off if the first string can completely match the second string This quantity is recorded here as x Pay attention to the boundary again $i-plen-x>=j-x$ and $j>=x$
$dp[i][j]=max(dp[i][j],dp[i-plen-x][j-x])$

Code ：
https://codeforces.com/contest/476/submission/164898590

479E Riding in a Lift

Topic link ：
https://codeforces.com/problemset/problem/479/E

Ideas ：
use $dp[i][j]$ To count , representative In the i When the wheel , Arrive at j What is the number of layers , Transfer inside A differential array is used , The transfer formula is very simple

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

Just deal with the difference equation again

Code ：
https://codeforces.com/contest/479/submission/165296573

478D Red-Green Towers

Topic link ：

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

Ideas ：

use $dp[i][j]$ To indicate to the third i The number of layers is j The number of solutions , image 01 Backpack like state , Just transfer , Because the array can arrive 1e8 Put it directly here 01 Just scroll through the array
$dp[j]=(dp[j]+dp[j-i])$

When counting the answers Put all that meet the conditions $dp[i]$ Add all

Code ：
https://codeforces.com/contest/478/submission/165305903