线性动态规划

线性动态规划

LuoguP2285 打鼹鼠

【题目大意】\(n \times n\) 网格中，某些时刻鼹鼠会在某一个网格出现。你可控制一个机器人打鼹鼠，若 \(i\) 时刻鼹鼠在某网格中出现，而机器人也处于同一网格，则此鼹鼠可被杀死。

机器人每一时刻只能像相邻位置移动一格或原地不动，即 \((i, j)\) 网格移向 \((i-1, j), (i+1, j), (i, j-1), (i, j+1)\) 网格，机器人不能走出整个 \(n \times n\) 网格。

你可自由选定机器人的初始位置。

现在知道\(m\)只鼹鼠出现的时间\(t_i\)（按不降序给出）和地点\((x_i,y_i)\)，求杀死鼹鼠最大值。（注：同一地点在同一时刻仅会出现最多1只鼹鼠）

记\(dp_i\)为处理完第\(i\)只鼹鼠后的杀死数最大值。

\[dp_i=\max(1,\max\limits _{|x_i-x_j|+|y_i-y_j|\le t_i-t_j}^{1\le j<i}dp_j+1)\]

最终结果为\(\max\limits_{1\le i\le n}dp_i\)

【单调队列优化】LuoguP1725 琪露诺

【题目大意】对于序列\(A=\left \{ a_0, a_1,a_2,\cdots,a_n\right \},a_0=0\)，从0下标出发，当位于\(i\)下标时，可以跳跃到\([i+L,i+R]\)下标处并收集到达点的点数\(a_k\)，求最终跳出序列，即\(i>n\)时收集点数和的最大值。

设\(dp_i\)表示到达下标\(i\)时，收集点数的最大值，有：

\[dp_i=\max\limits _{i-R\le j\le i-L}dp_j+a_i\]

需要使用单调队列维护区间\(dp_{max}\)，算法时间复杂度为\(O(n)\)

参考解答 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N];
int q[N],len,head=1,tail=0,dp[N],n,l,r,ans=-1e9;
void add(int x)
{
    while(dp[q[tail]]<=dp[x]&&head<=tail) 
        tail--;
    q[++tail]=x;
    while(q[head]<=x-len) head++;
}
int main()
{
    scanf("%d%d%d",&n,&l,&r);
    len=r-l+1;
    for(int i=0;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) dp[i]=-1e9;
    for(int i=l;i<=n;i++)
    {
        add(i-l);
        dp[i]=dp[q[head]]+a[i];
    }
    for(int i=n-r+1;i<=n;i++)
        ans=max(dp[i],ans);
    printf("%d",ans);
    return 0;
}

【树状数组优化】【二分优化】LuoguP1439 两个排列的最长公共子序列

【题目大意】给出\(1,2,\cdots,n\)的两个排列\(P_1,P_2\)，求它们的最长公共子序列。

由题意可知，两个排列组成的集合是相同的，以\(p_1,p_2,\cdots,p_n\)映射为新序\(1,2,\cdots,n\)，对\(P_2\)应用此映射得\(a_1,a_2,\cdots,a_n\)，转求序列\(A\)的最长上升子序列。

记\(dp_i\)表示以\(a_i\)结尾的最长上升子序列，有如下转移关系：

\[dp_i=\max\limits_{1\le j<i,a_j<a_i}dp_j+1,ans=\max\limits_{1\le i\le n}dp_i\]

暴力枚举的时间复杂度为\(O(n^2)\)

（1）考虑二分优化：记\(f_i\)表示上升子序列长度为\(i\)序列结尾元素最小值，\(F\)一定单调不减，故二分查找最大的\(f_j,f_j<a_i\)

（2）考虑树状数组优化：每一轮循环做：\(dp_i=query(a_i)+1,add(a_i,dp_i)\)即可。

时间复杂度为\(O(n\log n)\)

LuoguP1439 两个排列的最长公共子序列二分优化实现 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int dp[N],f[N],ans,n,a[N],b[N],c[N];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) f[i]=1e9;
    for(int i=1;i<=n;i++) 
        scanf("%d",&a[i]),c[a[i]]=i;
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]),b[i]=c[b[i]];
    for(int i=1;i<=n;i++)
    {
        if(b[i]<f[1]) dp[i]=1,f[1]=min(f[1],b[i]);
        else
        {
            int num=lower_bound(f+1,f+n+1,b[i])-f-1;
            dp[i]=num+1;
            f[dp[i]]=min(f[dp[i]],b[i]);
        }
        ans=max(ans,dp[i]);
    }
    cout<<ans;
    return 0;
}
LuoguP1439 两个排列的最长公共子序列树状数组实现 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int t[4*N],n,a[N],b[N],c[N],ans,dp[N];
void add(int x,int k)
{while(x<=n) t[x]=max(t[x],k),x+=x&(-x);}
int query(int x)
{
    int res=0;
    while(x) res=max(res,t[x]),x-=x&(-x); 
    return res;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) 
        scanf("%d",&a[i]),c[a[i]]=i;
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]),b[i]=c[b[i]];
    for(int i=1;i<=n;i++)
    {
        int cur=query(b[i]-1);
        if(!cur) dp[i]=1;
        else dp[i]=cur+1;
        add(b[i],dp[i]);
        ans=max(ans,dp[i]);
    }
    cout<<ans;
    return 0;
}

【相关习题】LuoguP1091 合唱队形

【二分优化】【序】LuoguP1020 导弹拦截

【题目大意】求序列\(A\)的最长不递增子序列长度与将\(A\)划分为若干不交的不递增子序列的最小划分数。

Dilworth定理

引理：Dilworth定理：对有限偏序集\(S\)和其上的偏序\(\preceq\)，\(S\)的宽度（最长反链\(L\)长度）等于最小的链覆盖数。

证明1

数学归纳法：记链覆盖集合为\(T\)，当\(|S|\le 3\)时，命题显然成立。当\(|S|=p\)时，假设\(|S|<p\)的所有情况均满足命题，可以记向某个\(S'(S'\subset S,|S'|=p-1)\)中插入元素\(e\)，得到\(S\)。

（1）若插入\(e\)使得反链长度增加1，则对于原反链序列\(L=\left \{ l_1,l_2,\cdots,l_{|L|}\right \}\)，\(\exists t_i,t_{i+1}\in T,t_i\succeq e\succeq t_{i_1}\)，可以证明$|T|\ge $\(|L|+1\)，而对于链覆盖的划分，可以在\(S'\)的基础上给\(e\)单独划一条链，\(|T|\le|L|+1\)，故\(|T|=|L|+1\)。

（2）若插入使得反链长度不增加，则一定有（1）不成立，必然存在链上一点\(l_i\)，

证明2

数学归纳法：当\(|S|\le 3\)时，成立。

设命题对所有元素个数小于\(|S|\)的偏序集均成立，令\(S\)的宽度为\(d\)，若\(S\)中所有元素均不可比，命题显然成立，否则在\(S\)中取一条长度大于1的链，令其最小元为\(m\)，最大元为\(M\)。

令\(T=S-\left \{ m,M \right \}\)，若\(T\)中的宽度不超过\(d-1\)，由归纳假设知\(T\)可被至多\(d-1\)条链覆盖，进而可被这些链加上链\(\left \{ m,M \right \}\)覆盖，命题成立，否则说明\(T\)中的宽度也为\(d\)，令\(T\)中最长的反链为\(A\)。

考虑集合：

\[S^+=\left \{ x\in S|(\exists a\in A)a\preceq x\right \}\]
\[S^-=\left \{ x\in S|(\exists a\in A)a\succeq x\right \}\]

有以下性质：\(s^+\cup S^- = S,S^+\cap S^- = A,|S^+|,|S^-|<S\)

对\(S^+,S^-\)分别应用归纳假设，则这两个集合的最小链覆盖数为\(d\)，且这些链中恰好包含一个\(A\)中的元素\(a\)，设这些链分别为\(C_a^+,C_a^-\)，则\(\left \{ C_a^-\cup \left \{a\right \}\cup C_a^+\right \}\)是\(S\)的一个最小链覆盖，命题得证。

正向求最长不上升子序列（反向求最长不下降子序列），再正向求最长上升子序列即可。

第二小问的贪心实现：

LuoguP1020 导弹拦截引理实现 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,a[N],dp[N],f[N],ans;
int main()
{
    while(cin>>a[++n]);
    n--;
    for(int i=1;i<=n;i++) f[i]=1e9;
    dp[n]=1,f[1]=a[n],ans=1;
    for(int i=n-1;i>=1;i--)
    {
        if(a[i]<f[1]) dp[i]=1,f[1]=a[i];
        else
        {
            int cur=upper_bound(f+1,f+n+1,a[i])-f-1;
            dp[i]=cur+1;
            f[dp[i]]=min(f[dp[i]],a[i]);
        }
        ans=max(ans,dp[i]);
    }
    cout<<ans<<endl;
    for(int i=1;i<=n;i++) f[i]=1e9,dp[i]=0;
    dp[1]=1,f[1]=a[1],ans=1;
    for(int i=2;i<=n;i++)
    {
        if(a[i]<=f[1]) dp[i]=1,f[1]=a[i];
        else
        {
            int cur=lower_bound(f+1,f+n+1,a[i])-f-1;
            dp[i]=cur+1;
            f[dp[i]]=min(f[dp[i]],a[i]);
        }
        ans=max(ans,dp[i]);
    }
    cout<<ans;
    return 0;
}
LuoguP1020 导弹拦截二分实现 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,a[N],dp[N],f[N],ans;
int main()
{
    while(cin>>a[++n]);
    n--;
    for(int i=1;i<=n;i++) f[i]=1e9;
    dp[n]=1,f[1]=a[n],ans=1;
    for(int i=n-1;i>=1;i--)
    {
        if(a[i]<f[1]) dp[i]=1,f[1]=a[i];
        else
        {
            int cur=upper_bound(f+1,f+n+1,a[i])-f-1;
            dp[i]=cur+1;
            f[dp[i]]=min(f[dp[i]],a[i]);
        }
        ans=max(ans,dp[i]);
    }
    cout<<ans<<endl;
    for(int i=1;i<=n;i++) f[i]=0;
    ans=1;f[1]=a[1];
    for(int i=2;i<=n;i++)
    {
        if(a[i]>f[ans]) f[++ans]=a[i];
        else
        {
            int cur=lower_bound(f+1,f+ans+1,a[i])-f;
            f[cur]=a[i];
        }
    }
    cout<<ans;
    return 0;
}
LuoguP1020 导弹拦截树状数组优化、引理实现（略）

【线段树优化】【动态规划】ABC408F Athletic

【题目大意】\(N\)个脚手架，第\(i\)个脚手架的高度为\(H_i\)，任选某脚手架开始，持续移动到其他脚手架，从脚手架\(i\)移动到脚手架\(j\)当且仅当\(H_j\le H_i-D,|i-j|\le R\)，求最多移动次数。

注意：\(H\)序列定为\(1\sim N\)的排列

ABC408F Athletic参考实现 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
struct node{int h,i;}a[N];
struct tree{int l,r,maxdp;}t[N*4];
bool cmp(node x,node y){return x.h>y.h;}
int n,ans,D,R,dp[N];
void build(int p,int l,int r)
{
    t[p].l=l,t[p].r=r;
    if(l==r) return;
    int mid=l+r>>1;
    build(2*p,l,mid),build(2*p+1,mid+1,r);
}
void change(int p,int x,int k)
{
    if(t[p].l==t[p].r){t[p].maxdp=k;return;}
    int mid=t[p].l+t[p].r>>1;
    if(x<=mid) change(2*p,x,k);
    else change(2*p+1,x,k);
    t[p].maxdp=max(t[2*p].maxdp,t[2*p+1].maxdp);
}
int query(int p,int l,int r)
{
    if(l<=t[p].l&&r>=t[p].r)
        return t[p].maxdp;
    int res=0,mid=t[p].l+t[p].r>>1;
    if(l<=mid) res=max(res,query(2*p,l,r));
    if(r>mid) res=max(res,query(2*p+1,l,r));
    return res;
}
int main()
{
    scanf("%d%d%d",&n,&D,&R);
    for(int i=1;i<=n;i++) 
        scanf("%d",&a[i].h),a[i].i=i;
    sort(a+1,a+n+1,cmp);
    build(1,1,n);
    for(int i=1;i<=n;i++)
    {
        dp[i]=max(dp[i],1);
        change(1,a[i].i,dp[i]);
        if(i+D<=n)
            dp[i+D]=1+query(1,max(1,a[i+D].i-R),min(n,a[i+D].i+R));
    }
    for(int i=1;i<=n;i++) ans=max(ans,dp[i]);
    cout<<ans-1;
    return 0;
}