线性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; 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紫书的习题。
