算法竞赛进阶指南 0x50 总论
2022/7/15 1:22:37
本文主要是介绍算法竞赛进阶指南 0x50 总论,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录- AcWing895. 最长上升子序列
- 方法一
- 方法二
- 当询问最长子序列是哪些的时候
- 896. 最长上升子序列 II
- 思路
- O(NlogN)做法:贪心+二分
- 代码
- AcWing\897. 最长公共子序列
- 思路
- 代码
- AcWing898. 数字三角形
- 思路
- AcWing895. 最长上升子序列
- 参考资料
AcWing895. 最长上升子序列
方法一
采用从前往后推的方法
#include <bits/stdc++.h> using namespace std; #define N 1006 typedef long long ll; ll a[N]; ll f[N]; int main() { int n; scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%lld", a+i);//注意:我存储的是ll,所以输入也应该是lld f[0] = 0;//注意:初始条件一定要给 a[0] = INT_MIN;//注意:对于这种有对比的情况,是要更改一下原数组的第一个元素 for(int i = 0; i < n; i++) for(int j = i+1; j <= n; j++) if(a[j] > a[i]) { f[j] = max(f[j], f[i]+1); } ll ans = 0; for(int i = 1; i <= n; i++)//注意:这里的最优解并不是从最后一个元素里面找,而是在1~N中找 { ans = max(ans, f[i]); } cout << ans; return 0; }
方法二
思考这一种状态可以由哪些推过来
#include <bits/stdc++.h> using namespace std; #define N 1006 typedef long long ll; ll a[N]; ll f[N]; int main() { int n; scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%lld", a+i); f[0] = 0;//注意:初始条件一定要给 a[0] = INT_MIN;//注意:对于这种有对比的情况,是要更改一下原数组的第一个元素 for(int i = 1; i <= n; i++) for(int j = 0; j < i; j ++) { if(a[j] < a[i]) { f[i] = max(f[i], f[j]+1); } } ll ans = 0; for(int i = 1; i <= n; i++) { ans = max(ans, f[i]); } cout << ans; return 0; }
当询问最长子序列是哪些的时候
#include <bits/stdc++.h> using namespace std; #define N 1006 typedef long long ll; ll a[N]; ll f[N]; ll path[N]; void Print(int i) { if(i==0) return; Print(path[i]); cout << a[i] << ' '; } int main() { int n; scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%lld", a+i); f[0] = 0;//注意:初始条件一定要给 a[0] = INT_MIN;//注意:对于这种有对比的情况,是要更改一下原数组的第一个元素 for(int i = 1; i <= n; i++) for(int j = 0; j < i; j ++) { if(a[j] < a[i]) { if(f[i] < f[j]+1) { path[i] = j;//并不需要把之前的全部存起来,只需要知道从哪里转移过来就行了 f[i] = f[j]+1; } } } ll ans = 0; ll pos = 0; for(int i = 1; i <= n; i++) { if(f[i] > ans) { ans = f[i]; pos = i; } } Print(pos); puts(""); cout << ans; return 0; }
896. 最长上升子序列 II
思路
这一道题目不能再使用动态规划来进行求解
必须采用更为快速的
O(NlogN)做法:贪心+二分
a[i]表示第i个数据。
dp[i]表示表示长度为i+1的LIS结尾元素的最小值。
利用贪心的思想,对于一个上升子序列,显然当前最后一个元素越小,越有利于添加新的元素,这样LIS长度自然更长。
因此,我们只需要维护dp数组,其表示的就是长度为i+1的LIS结尾元素的最小值,保证每一位都是最小值,这样子dp数组的长度就是LIS的长度。
dp数组具体维护过程同样举例讲解更为清晰。
同样对于序列 a(1, 7, 3, 5, 9, 4, 8),dp的变化过程如下:
- dp[0] = a[0] = 1,长度为1的LIS结尾元素的最小值自然没得挑,就是第一个数。 (dp = {1})
- 对于a[1]=7,a[1]>dp[0],因此直接添加到dp尾,dp[1]=a[1]。(dp = {1, 7})
- 对于a[2]=3,dp[0]< a[2]< dp[1],因此a[2]替换dp[1],令dp[1]=a[2],因为长度为2的LIS,结尾元素自然是3好过于7,因为越小这样有利于后续添加新元素。 (dp = {1, 3})
- 对于a[3]=5,a[3]>dp[1],因此直接添加到dp尾,dp[2]=a[3]。 (dp = {1, 3, 5})
- 对于a[4]=9,a[4]>dp[2],因此同样直接添加到dp尾,dp[3]=a[9]。 (dp = {1, 3, 5, 9})
- 对于a[5]=4,dp[1]< a[5]< dp[2],因此a[5]替换值为5的dp[2],因此长度为3的LIS,结尾元素为4会比5好,越小越好嘛。(dp = {1, 3, 4, 9})
- 对于a[6]=8,dp[2]< a[6]< dp[3],同理a[6]替换值为9的dp[3],道理你懂。 (dp = {1, 3, 5, 8})
这样子dp数组就维护完毕,所求LIS长度就是dp数组长度4。
通过上述求解,可以发现dp数组是单调递增的,因此对于每一个a[i],先判断是否可以直接插入到dp数组尾部,即比较其与dp数组的最大值即最后一位;如果不可以,则找出dp中第一个大于等于a[i]的位置,用a[i]替换之。
这个过程可以利用二分查找,因此查找时间复杂度为O(logN),所以总的时间复杂度为O(N*logN)转载自 紫芝 https://blog.csdn.net/qq_40507857/article/details/81198662 CSDN[1]
这道题目恰恰使用到了贪心的思想。
dp
数组里面存放了(当前当前位置之前,所有)长度为 i 的上升子序列的最小的末尾元素(只需要一个代表元,那就是结尾的元素)
依次从左向右进行扫描,对比 a[ i ] 和dp数组里面的值。
- 如果
a[i]
的值大于dp
数组的最后一个值,那么由于a[i]
的加入,就会让最长子序列长度增加。 - 如果
a[i]
的值小于等于dp
数组的最后一个元素,找一个大于等于a[i]
的第一个元素的下标p。
p之前的数字全部比 a 小,a 可以替换p的位置,完全合法,并且让p的位置的数字更小,更可能出现较长的上升子序列。
代码
#include <bits/stdc++.h> using namespace std; #define N 100020 int a[N], dp[N]; int m = 0; int main() { int n; scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", a+i); dp[1] = a[1]; m = 1; for(int i = 2; i <= n; i++) { if(a[i] > dp[m]) { dp[++m] = a[i]; continue; } int p = lower_bound(dp+1, dp+1+m, a[i])-(dp+1)+1; dp[p] = a[i]; } printf("%d", m); return 0; }
竟然更加简单:)
AcWing\897. 最长公共子序列
思路
闫氏DP分析法
-
状态:
dp[i][j]
代表在A序列里面以i
结尾,在B中j
结尾的序列。- 子结构:A中以
i
结尾,在B中j
结尾的序列中所有的公共子序列。 - 最优子结构:最长的公共子序列
- 状态表示:使用一个整数,表示长度。
- 子结构:A中以
-
转移:
对于dp[i][j]
一共有以下四种情况:-
包含
a[i]
,包含b[j]
;
注意有前提条件:a[i] == b[j]
这时候状态表示是dp[i-1][j-1]+1
-
包含
a[i]
,不包含b[j]
;
没有办法求得这种情况的等价情况。
但是有一个集合可以满足要求:dp[i][j-1]
这一个集合有两种情况- 包含
a[i]
,不包含b[j]
- 不包含
a[i]
,不包含b[j]
这是因为我的状态表示仅仅说明是
a[1~i]
和b[1~j]
的最长的公共子序列,包不包含a[i]
我并不知道。 - 包含
-
不包含
a[i]
,包含b[j]
; 和上面一致! -
不包含
a[i]
,不包含b[j]
。 显然是dp[i-1][j-1]
-
由于有重复情况,所以最终dp方式见代码
代码
#include <bits/stdc++.h> using namespace std; #define N 1020 char a[N], b[N]; int dp[N][N]; int main() { int n, m; scanf("%d%d", &n, &m); scanf("%s", a+1); scanf("%s", b+1); for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { dp[i][j] = max(dp[i-1][j], dp[i][j-1]); if(a[i] == b[j]) dp[i][j] = max(dp[i-1][j-1]+1, dp[i][j]); } } printf("%d", dp[n][m]); return 0; }
AcWing898. 数字三角形
输入样例:
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
输出样例:
30
思路
这一道题目给定的三角不便于存储,要想办法改变一下。我们可以使用样例中的办法进行存储
这样,对应的规则就变成了向下或者向右下方走。
#include <bits/stdc++.h> using namespace std; #define N 506 int a[N][N]; int dp[N][N]; #define WAY2 //更换上面这一个定义,可以使用两种方法! int main() { int n; scanf("%d", &n); for(int i = 1; i <= n; i++) for(int j = 1; j <= i; j++) dp[i][j] = -0x3f3f3f3f; for(int i = 1; i <= n; i++) for(int j = 1; j <= i; j++) scanf("%d", &a[i][j]); #ifdef WAY1 dp[1][1] = a[1][1]; for(int i = 1; i < n; i++) for(int j = 1; j <= i; j++) { dp[i+1][j] = max(dp[i+1][j], dp[i][j]+a[i+1][j]); dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+a[i+1][j+1]); } #endif #ifdef WAY2 dp[1][1] = a[1][1]; for (int i = 2; i <= n; i++) for(int j = 1; j <= i; j++) { if(j > 1)dp[i][j] = max(dp[i][j], dp[i-1][j-1] + a[i][j]);//注意两个边界条件的判断 if(j< i ) dp[i][j] = max(dp[i][j], dp[i-1][j]+a[i][j]); } #endif int ans = -0x3f3f3f3f; for(int i = 1; i<= n; i++) { ans = max(ans, dp[n][i]); } printf("%d", ans); return 0; }
参考资料
转载自 紫芝 https://blog.csdn.net/qq_40507857/article/details/81198662 CSDN ↩︎
这篇关于算法竞赛进阶指南 0x50 总论的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-19永别了,微服务架构!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?