线性dp

线性dp

一般的线性递推式

\( a_n = \sum_1^m c_i a_{n-i}\)

特别的,m=2, \(c_1 = c_2 = a_1 = a_2 = 1\), 为斐波那契数列。
解决的方法:

  • 通项公式。然而在算法竞赛中并不适用
  • 快速幂(此时应该复习一波矩阵的乘法)
  • OEIS大法

最长上升子序列(严格单调增)

一般的解法:

更优的解法:O(nlogn)

  • 状态:dp[i]: 长度为i的上升子序列的最末元素.若有多个长度为i的上升子序列,则记录其中最小的。那么dp[i] < dp[i+1],即dp[]单调增
  • 对于每个\(A_i\),找j满足\(d_{j-1}<A_i \le d_j\), 然后令\(d_j = A_i\)
  • j可以使用二分查找lower_bound()

代码

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
int num[maxn];
int dp[maxn];
int n;
int LIS(){
int len = 1;
dp[0] = num[0];
for(int i=1; i<n; i++){
if(num[i]>dp[len-1])
dp[len++] = num[i];
else
dp[lower_bound(dp, dp+len, num[i])-dp] = num[i];
}
return len;
}
int main(){
while(~scanf("%d", &n)){
for(int i=0; i<n; i++) scanf("%d", &num[i]);
printf("%d\n", LIS());
}
}

若记录数字,那么就相当于记录一个前面的路径即可.(路径是逆序的)

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
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
int num[maxn];
int dp[maxn];
int id[maxn];
int n;
/*
7
1 5 3 4 6 2 7
*/
int pre[maxn];
int LIS(){
int len = 1;
dp[0] = num[0];
pre[0] = -1;
id[0] = 0;
for(int i=1; i<n; i++){
if(num[i]>dp[len-1]){
pre[i] = id[len-1];
id[len] = i;//记录点的编号
dp[len++] = num[i];
}
else{
//若要替换新的点,记录这个点前面的编号
int index = lower_bound(dp, dp+len, num[i])-dp;
id[index] = i;
pre[i] = pre[index];
dp[index] = num[i];
}
}
return len;
}
int main(){
while(~scanf("%d", &n)){
for(int i=0; i<n; i++) scanf("%d", &num[i]);
int ans = LIS();
int index;
for(int i=0; i<n; i++){
if(num[i] == dp[ans-1]){
index = i;
break;
}
}
printf("%d\n", ans);
printf("%d ", num[index]);
while(pre[index] != -1){
printf("%d ", num[pre[index]]);
index = pre[index];
}
}
}

题目

数字三角形②
路径的权值mod m的最大值

  • 表示状态:f[i][j][k]:表示第i行第j列的路径和mod m是否等于k,记录一个bool值。
  • 答案:最后扫描一遍最后一行就可以了

数字三角形③
路径必须要经过中间的某个点:

  • method①:将这一行将数字三角形分成两部分,做两遍dp.
  • method②:将必须经过的点设置一个非常大的权值,从而dp的时候较大的值一定会选择这个点。最后的答案减去这个比较大的值就行了。

未解决的问题

补充lrj紫书的习题。

文章目录
  1. 1. 一般的线性递推式
  2. 2. 最长上升子序列(严格单调增)
    1. 2.0.1. 更优的解法:O(nlogn)
      1. 2.0.1.1. 代码
  • 3. 题目
  • 4. 未解决的问题
  • {{ live2d() }}