C++知识点总结(58)：序列型动态规划

一、基础

1. 意义

动态规划（dynamic programming，简称 dp），将一个目标大问题“大事化小，小事化了”，分成很多的子问题，得出子问题的解后得到目标大问题的解。动态规划相当于地狱难度的递推。

2. 序列 dp 解法

序列型动态规划分为几种常见的问题：

• 取连续的子段（串）
  • dp[i] 表示以 $i$ 为结尾
• 取子序列（不要求连续）
  • dp[i] 表示以 $i$ 为结尾
  • dp[i] 表示 $0\sim i$ 中 …
  • dp[i] 长度为 $i$ 序列结尾的性质
• 分段
  • dp[i] 表示以 $i$ 为结尾

二、例题

1. 最大子段和

题目描述

给出数组 $a$，如果我们取连续且非空的一段，那么这段的和最大是多少?

输入描述

第 $1$ 行，是一个正整数 $n$，数组 $a$ 的长度。
第 $2$ 行，用空格隔开的 $n$ 个整数，依次是 $a[1]\sim a[n]$ 的值。

输出描述

$1$ 个整数，为所求的最大的和

样例1

输入

6
1 -6 5 -4 2 4

输出

7

提示

【样例解释】
取 $5,-4,2,4$ 可以得到最大的和 $7$。
【数据范围】
对于 $60\%$ 的数据，$n\le 100$。
对于 $80\%$ 的数据，$n\le 5000$。
对于 $100\%$ 的数据，$n\le 100000$。

【问题类型】 取子段
【问题解法】 dp[i] 表示以 a[i] 为结尾的最大子段和是多少
【模板技巧】 如果前面都是负数，我不跟它们同流合污（a[i]）；如果前面大的，那就加入它们，做一个更大的数（dp[i-1]+a[i]）
【参考答案】

#include<bits/stdc++.h>
using namespace std;
int n,maxn=-1e8;
int a[100005];
int dp[100005];
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];dp[1]=a[1];for(int i=2;i<=n;i++){dp[i]=max(a[i],dp[i-1]+a[i]);maxn=max(maxn,dp[i]);}cout<<maxn;return 0;
}

2. 删数最大子段和（数据强度：pro max）

给出一个数组 a[]，删除一个元素后，求它的最大子段和。（子段是指数组中连续的一段元素）删除的元素可以由你自由选择，但是不能不删除任何元素，输出你能得到的最大的子段和。

思路：要删掉 a[i] 的时候会产生两个切口，第一个是以 a[i-1] 为结尾，第二个是以 a[i+1] 为开头。以 a[i-1] 为结尾取一个非常大的子段，以 a[i+1] 为开头取一个非常大的子段，将它们组合在一起，就可以完成本题。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e6+8;
const int NEGINF=-1e18;
int n,ans=NEGINF;
int a[MAXN],dpl[MAXN],dpr[MAXN];
/*
* dpl[i]:以i为右端点的最大子段和
* dpr[i]:以i为左端点的最大子段和
*/
signed main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)dpl[i]=max(dpl[i-1]+a[i],a[i]);for(int i=n;i>=1;i--)dpr[i]=max(dpr[i+1]+a[i],a[i]);for(int i=1;i<=n;i++)ans=max({ans,dpl[i-1],dpr[i+1],dpl[i-1]+dpr[i+1]});//选择左边/右边/左边和右边cout<<ans;return 0;
}

3. 最长上升子序列（数据强度：pro max）

求出数组 a[] 的最长上升子序列⻓度。

参考答案：

#include<bits/stdc++.h>
using namespace std;
int n,sz;
int a[5005];
int dp[5005];
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){if(sz==0||a[i]>dp[sz])sz++,dp[sz]=a[i];else{int p=lower_bound(dp+1,dp+sz+1,a[i])-dp;dp[p]=a[i];}}cout<<sz;return 0;
}

4. 3 或 5 的倍数序列

给出一个序列 a[]，要求你从中找出一个子序列，满足子序列中任意相邻两数之和是 $3$ 或 $5$ 的倍数。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e3+8;
const int MOD=1e9+7;
int n,a[MAXN],dp[MAXN];
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];int ans=0;for(int i=1;i<=n;i++){for(int j=1;j<i;j++)if((a[i]+a[j])%3==0||(a[i]+a[j])%5==0)dp[i]=(dp[i]+dp[j]+1)%MOD;ans=(ans+dp[i])%MOD;}cout<<ans;return 0;
}

5. 数码约数序列

给出一个序列 a[]，要求你从中找出一个子序列，满足子序列中任意相邻两数，前一个数的末位数码是后一个数的首位数码的约数。
例如 $302,817,739000$ 是一个满足要求的序列，因为 $302$ 的末位 $2$ 是 $807$ 的首位 $8$ 的约数；$817$ 的末位 $7$ 是 $739000$ 的首位 $7$ 的约数。 但是 $70,1$ 就不满足要求，因为 $0$ 不是 $1$ 的约数。
问所有满足要求的子序列中，总和最大的序列的和是多少？（单独一个数也算满足要求的序列）

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+8;
long long n,dp[MAXN][10];
int main(){cin>>n;for(int i=1,a,fst,lst;i<=n;i++){cin>>a,fst=a,lst=a%10;while(fst>=10)fst/=10;for(int j=0;j<=9;j++)dp[i][j]=dp[i-1][j];for(int j=1;j<=fst;j++)if(fst%j==0)dp[i][lst]=max(dp[i][lst],dp[i-1][j]+a);}long long ans=0;for(int i=0;i<=9;i++)ans=max(ans,dp[n][i]);cout<<ans;return 0;
}