[learning notes] DP status and transfer

Ehab and the Expected GCD Problem

Thinking is still a step slow .

observations + dp .

This problem is difficult dp Stage design . Let's consider filling in the sequence from front to back , At the same time, record the current prefix gcd state .

dp[i][j][k] Before considering i Number , Prefix $\gcd =2^{\text{j}}{3}^{\text{k}}(k=0/1)$ . The transfer is ingenious .（ Multiplication principle ）

Three Servers

After reading the title, I am joker …

Simple knapsack problems can make you doubt life …

Accessibility dp -> Optimality dp

observations + dp

Both are accessibility dp ：https://blog.csdn.net/cqbzlydd/article/details/124870640?spm=1001.2014.3001.5501

Hero meet devil

It's better to press the question .

observations + dp

Min Product Sum

dp（x）
mathematics （v）

Dry stare method …

Why can't I understand the solution

Salvage Robots

Shocked …

Forcibly construct the state and dp Stage …

Worship idsy …

Consider a safe area in the middle … There are dangerous areas around …

Consider dragging the safety zone , Some of these dangerous areas robot Will be thrown out …

set up $dp[a][b][c][d]$ Indicates that the upper left corner of the safety area is $(a,b)$, The lower right corner is $(c,d)$ , It can be saved in a dangerous area robot Maximum number of .

As for transfer , Preprocessing Up[i][l][x] It means the first one i Column [1,l] Of robot Move up no more than x Step by step E The number of

Up, down, left and right directions are similar .

When transferring, consider the safety zone to shrink inward ：

$dp[a][b][c][d]+?\to dp[a][b+1][c][d]$

The four directions up, down, left and right are the same .

answer $\max (dp[i][j][i][j]+1)(s[i][j]=o)$ . Because the last one robot It must be safe .

The state and stage of this question are too difficult to think of . Rather call it structure dp topic .

Prefix Median

AGCAGCAGC