[learning notes] simple DP

It may not be simple

thank C202044zxy The courseware and wonderful explanation prepared by the senior students .

Treatment plan

• Be careful dp Dimensional consciousness of
• We instinctively take time as the dimension dp , However, it is difficult to continue
• Start from the dimension of planning prefix ,$d{p}_i$ It means that you will $[1,r_i]$ The minimum cost of a total cure
• We instinctively press $r_i$ Sort , about $j<i$ The situation of , according to $T_i<T_j$ and $T_i>T_j$ Classification discussion can get a very reasonable transfer formula ：
• $d{p}_i=d{p}_j+c_i(r_j-l_i+1\ge |T_i-T_j|)$
• such $O(n^2)$ Of $dp$ You'll get 0pts Good result ！
• The reason is that we don't realize $j>i$ Time can also be transferred , Draw a picture to show that the transfer mode is rather the same
• therefore dp The stage is not obvious , Because there may be a curve to save the country （ Time is influencing ）
• Analyze the special properties of the transfer equation , Think of the shortest path optimization （ Remove the absolute value trick Don't say ）
• Time complexity O(mlogm) （ Praise for the author ！）

Lanterns

• This question is also difficult
• This problem is difficult in state design I know the routine ！
• The most basic state is $d{p}_{i,j}$ Indicates that the processing is finished $[1,i]$ The longest prefix after the lantern of is $j$ Is it feasible
• So the number of States $O(n^2)$
• The problem is that we don't realize dp Values can also be used to describe dimensions
• set up $d{p}_i$ Indicates that the processing is finished $[1,i]$ The longest prefix that can be covered after the lantern
• Then there is the classified discussion . Just pay attention to the sub problem .（ Cuckoo

Favorite Game

• It's really simple dp , however cf score 3300 It must not be simple
• This question involves many dimensions , But experienced oier Excluding me Can write basic dp
• $dp[S][i][j]$ Indicates that the set passing through the portal is S , Currently in place i , Did j Minimum time for tasks
• This looks stupid dp It actually contains all dimensions , Time complexity $2^{14}\times 100^3$
• If at the portal , Do not care about location , If in the landmark , Don't care about time
• This enlightens us on dp Dimension reduction
• set up f[S][i] Indicates that you are currently at the portal , complete i Minimum time for tasks ,g[S][i] It's on the second day i Landmarks , Maximum number of tasks completed .
• We can give a similar classification discussion to dp Dimension reduction . Time complexity $2^{14}\times 100^2$

Group Projects

• This question is really not difficult But I really stuck for a long time
• The simple way is ,dp[i][j][k] Before presentation i Number , Yes j Group has no maximum value , The minimum sum is k Number of alternatives
• So the number of States $O(n^{3}m)$ In situ explosion
• Would you rather think of using $k\le 1000$ To optimize
• But rather, my approach k Will be far more than the given 1000
• It is also appropriate to be robbed , Even a little dp Skills have not accumulated to
• We assume that a[i] Is the current maximum , Calculate the sum of disharmony at this time , This dimension satisfies <=1000
• Number of final states $O(n^{2}m)$