当前位置：网站首页>1D / 1D dynamic programming learning summary

1D / 1D dynamic programming learning summary

2022-04-23 09:43:00 【Zimba_】

Preface ：

Since the discovery 1D/1D After dynamically planning this new skill block , Every time I see this kind of topic, I can say hi and succeed , Then my teammates urged me to learn . Furthermore, it is found that there are many optimization methods , So take your time , Learn a little every day , Plus, I have to do some strange questions to keep my state , That's about it .

The first 0 God （1D/1D Dynamic programming ）

What is? 1D/1D Dynamic programming ？
1D/1D Dynamic programming It is shaped like $dp_{i}=max\{ dp_{j}+w(i,j)\}$ Dynamic planning of , Of course $m a x$ It can also be replaced by $m i n$ .
It is said that people who look like this $d p$ Generally, it can be optimized to $o (n l o g n)$ .
The idea of optimization is to $j$ In the range of , Quickly find an optimal transfer point .
The learning idea is probably Learn the different types of this transfer equation , Then learn its optimization method for each type .
Learning links （ Go for more walks , In this way, the author will not feel guilty after stealing knowledge , Blog will add their own things （ Maybe ））

The first 0.5 God （ Prefixes and optimizations ）

There is one Prefixes and optimizations , The author defaults to , Don't learn . If not, please study by yourself .

The first 1 God （ Monotonic queue optimization ）

ah ~ New power ！
It's today Monotonic queue optimization dp, Of course , Just think everyone will be in a monotonous queue .
To be honest , After learning, I feel the original $d p$ The formula is also a little inappropriate , We put $dp_{j}$ Also regarded as $w (i, j)$ in $j$ Part of the operation , That formula is actually $dp_{i}=max\{ w(i,j)\}$ .
Okay , Let's get to the point .
According to our learning ideas , We should be for such optimizations , There is an inductive transfer formula , Then there is .

Transfer equation

$dp_{i}=max\{ w(j)\}$

explain

This equation means $d p$ The transfer of is only related to $j$ of . And then this $j$ Well , It's usually an interval range , And with $i$ The increase of , $j$ The range of is shifted to the right as a whole . This ensures that it can be transferred , Use monotone queues to find the best .

Ideas ：

The note mentions $j$ The range of the is shifted to the right as a whole , We set the transfer $dp_{i-1}$ when $j$ The range of is $l_{i-1},r_{i-1}]$ , Transfer $dp_{i}$ when $j$ The range of is $l_{i},r_{i}]$ . Then we $r$ When it gets bigger , Just add the new element to the right of the monotone queue （ If you want to add , Before that, take away some unwanted elements on the right ）, Then the answer is found on the left side of the queue . Of course , It's all monotonous stuff , Let's not go into details .

Practical examples

PTA-Little Bird

The question

$n$ tree , Each tree has a height $d_{i}$ , Small $H$ In the $1$ On a tree , To jump to the $n$ On a tree . In the $i$ On a tree , You can jump to $i, i + 1, \dots, i + k$ On a tree . Every time , If the height is not less than the original height , The fatigue value will increase $1$ . Now ask little $H$ From $1$ Jump up a tree to the $n$ On a tree , What is the minimum fatigue value .
$(1\leq n\leq k\leq 10^{6})$

Ideas

We set the State $dp_{i}$ Jump to the $i$ The minimum amount of fatigue that needs to be spent on a tree .
So there's a transfer equation $dp_{i}=min\{dp_{j}+[d_{i}>=d_{j}]\}$ , among $j\in [i-k,i-1]$ .

We should learn this idea .
First of all, let's observe $j\in [i-k,i-1]$ , We find that the interval increases with $i$ Enlarge and move the whole right , establish .
then $dp_{j}+[d_{i}>d_{j}]$ , It's about $i$ and $j$ The formula of , Er, it doesn't seem to hold water .
At this time, we can only use our intelligence , Cough .
Let's find out first $dp_{i}$ Monotony doesn't go down , And each increase is an increase of $1$ . So for two $dp_{j}$ Value , We must take the smaller one directly , Because the little one $+ 1$ No more than big . Then for two identical $dp_{j}$ , We must give priority to $d_{j}$ The big one , That is to find a way to make $dp_{j},d_{j})$ maximal $j$ . In this way, you can optimize with monotone queue .

Just demonstrated that the car overturned , I decided to use it. $dp_{i}=w(i,j),where\;g(j)\;is\;max\;for\;j\;in\;range$ As a new style .

So maybe we can generalize the model .

Code

The title has some cards , open o2 Optimization is over .
Finishing work .

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int q[1000005],fr,bk;
int d[1000005];
int dp[1000005];
int w(int i,int j)
{
    
    return dp[j]+(d[i]>=d[j]);
}
P g(int j)
{
    
    return P(-dp[j],d[j]);
}
int main()
{
    
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&d[i]);
    int m;
    scanf("%d",&m);
    while(m--)
    {
    
        fr=bk=0;
        int k;
        scanf("%d",&k);
        dp[1]=0;
        q[bk++]=1;
        for(int i=2;i<=n;i++)
        {
    
            while(q[fr]<i-k)fr++;
            dp[i]=w(i,q[fr]);
            while(!(fr==bk)&&g(q[bk-1])<=g(i))bk--;
            q[bk++]=i;
        }
        printf("%d\n",dp[n]);
    }
	return 0;
}

the second day （ Divide and conquer optimization ）

~~（ To be continued ..）~~
(upd: Updated that the title should not be followed by a colon bug)
Yesterday was about $j$ Independent transfer , basis $j$ The monotonicity of is optimized by monotone queue .
So today is not about $j$ Independent , Namely and $i$ and $j$ It's all about , Just learned a divide and conquer optimization , Of course, you have to divide and conquer first .

Transfer equation

$dp_{i}=max(w(i,j)),j \in [1,i-1]$
Or to say $dp_{i}=w(i,j),where\;g(i,j)\;is\;max\;for\;j\;in\;range$
And it also needs its transfer , With $i$ Satisfy some monotonicity of decision .

explain

All in all , We need to find the optimal transfer point and $i, j$ It's all about .
then , The transfer should follow $i$ Satisfy the monotonicity of decision . for instance , Roughly speaking , When $i$ It's getting bigger , The best decision point $j$ It will get bigger . But that doesn't mean $j$ Bigger is better , There are some $j$ It will not be regarded as the optimal decision point at all , Just what's for everyone $i$ As the optimal decision point $j$ We are following $i$ Bigger and bigger （ No drop ）.

Ideas

The general practice of divide and conquer is , Let's find the one in the middle first $dp_{mid}$ The transfer point of $q m i d$ . Then according to the monotonicity of the decision , When $i < m i d$ when , Transfer point $j\in[1,qmid]$ ; When $i > m i d$ when , Transfer point $j\in[qmid,n]$ And $j < i$ .
Then take the midpoint every time to find the optimal transfer point , Cut the interval into two halves . Recursion depth is $l o g$ Class , Then when we find the transfer point, we can violently traverse the decision interval where there may be the optimal transfer point . Overall complexity $o (n l o g n)$ .

Practical examples

Lightning Conductor

The question

Given a length of $n$ Sequence ${a_{n}\}$ , For each $i\in [1,n]$ , Find the smallest nonnegative integer $p$ , bring $\forall j\in[1,n]$ , There are $a_j\le a_i+p-\sqrt{|i-j|}$
$1\leq n\leq 5\times 10^{5},0\leq a_{i}\leq 10^{9}$

Ideas

We make $dp_{i}$ It means the first one $i$ Answer .
First , Get rid of the absolute value , We can run forward $d p$ , Run backwards again , Find a maximum .
So the forward transfer equation is $dp_{i}=max\{a_{j}-a_{i}+\sqrt{i-j}\},j\in [1,i-1]$ .
About $i$ Constant first , become $dp_{i}=max\{a_{j}+\sqrt{i-j}\}-a_{i},j\in [1,i-1]$ .
So now it's , What we call model transfer $dp_{i}=max\{w(i,j)\}$ , among $w(i,j)=a_{i}+\sqrt{i-j}$ .
then , It should satisfy what we call decision monotonicity , namely $i$ When it gets bigger , The optimal decision point we choose $j$ It will get bigger . Let's observe the formula $w_{j}(i)=a_{i}+\sqrt{i-j}$ It's a story about $i$ Function of , Yes $i - 1$ Functions like this , We're going to do it for every $i$
Choose the best function $w_{j}$ , Make the function value the highest .
Then we find that the growth rate of these functions slows down , And $w_{j}$ Than $w_{j+1}$ stay $i$ At the same time, the growth rate is slower . That is, once $i$ Grow to some point $w_{j}$ By a $w_{k}$ More than the , And $k > j$ , that $w_{j}$ There will never be a day to turn over .
in general , Is to meet when $i$ Bigger , The optimal decision point will only keep getting bigger （ Or change the question to smaller ）.
Satisfy the properties we mentioned earlier , Then we can divide and conquer .

Code ：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

double a[500005];
ll dp1[500005],dp2[500005];
double w(int i,int j)
{
    
    return a[j]+sqrt(abs(i-j))-a[i];
}
void solve(int l,int r,int ql,int qr,ll *dp)
{
    
    if(l>r||ql>qr)return ;
    int mid=(l+r)/2;
    int qmid=ql;
    for(int i=ql;i<=qr&&i<mid;i++)if(w(mid,i)>w(mid,qmid))qmid=i;
    dp[mid]=ceil(w(mid,qmid));
    solve(l,mid-1,ql,qmid,dp);solve(mid+1,r,qmid,qr,dp);
}
int main()
{
    
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lf",&a[i]);
    solve(1,n,1,n,dp1);
    reverse(a+1,a+n+1);
    solve(1,n,1,n,dp2);
    reverse(dp2+1,dp2+n+1);
    for(int i=1;i<=n;i++)printf("%lld\n",max(0ll,max(dp1[i],dp2[i])));
	return 0;
}