CI 疮了，我也疮了
查看代码源文件 Visit Cai1Hsu/blog 前往 GitHub
题符 「B3637 最长上升子序列」~ Easy 题目链接
思路 创建一个dp数组，记录arr[0..=i]间包含arr[i]的最大升序子序列 记录数据时，我们选择一个快指针i,表示子序列 的最后一项的下标，同时创建一个慢指针j,依次遍历arr[0..i]间的每一个值，如果arr[i] > arr[j],说明arr[i]和arr[j]可以构成升序子序列。我们令dp[i] = max(dp[j] + 1, dp[i])，因为dp[j]是包含arr[j]的最大子序列的长度，而arr[i]可以排在该子序列后面。 i, j 的状态如图:1 2 [2, 1, 3, 8, 5, 6, 7, 4, 10] j i
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 n = int (input ()) arr = list (map (lambda s: int (s), input ().split(' ' ))) dp = [1 ] * n ans = 1 for i in range (0 , n): for j in range (0 , i): if arr[i] > arr[j]: dp[i] = max (dp[i], dp[j] + 1 ) ans = max (ans, dp[i]) print (ans)
题符 「P1115 最大子段和」~ Normal 题目链接
思路 与上一道题相似，我们创建一个dp[]，其中dp[i]记录包含i的最大子序列和 。 这样定义的原因在于，当我们读取到下一个元素的时候，我们可以很容易判断是否需要加上下一个元素。因为如果arr[i + 1] > dp[i] + arr[i + 1]，我们应该让该子序列为[arr[i + 1]]，而其他时候则加上arr[i + 1]，同时，当和相等时，我们应尽量加上新的值，因为后面可能有机会使得整个序列的和更大。 考虑到我们并不需要已经使用过的值（arr[0..i+1]和dp[0..i+1），我们可以考虑只使用常数大小的空间。 代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include <bits/stdc++.h> using namespace std;int main () int n; cin >> n; int queue; cin >> queue; int ans = queue; for (int i = 1 ; i < n; i++) { int t; cin >> t; queue = max (t, queue + t); ans = max (ans, queue); } cout << ans; }
题符 「P8707 走方格」~ Hard 题目链接
思路 最简单DP题，对于每一个点Matrix[i, j]，走到它的方法为上面的点和左边的点的方法之和。
Complaint 为什么不用.NET! 为什么不支持C# 12.0!
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 var vi = Console.ReadLine()! .Split(' ' ) .Select(int .Parse); int n = vi.First(), m = vi.Last();int [,] matrix = new int [n, m];for (int i = 0 ; i < n; i++) matrix[i, 0 ] = 1 ; for (int i = 0 ; i < m; i++) matrix[0 , i] = 1 ; for (int i = 1 ; i < n; i++){ for (int j = 1 ; j < m; j++) { if (i % 2 != 1 || j % 2 != 1 ) matrix[i, j] = matrix[i - 1 , j] + matrix[i, j - 1 ]; } } Console.WriteLine(matrix[n - 1 , m - 1 ]);
题符 「P1216 数字三角形 Number Triangles」~ Lunatic 题目链接
思路 我们从三角形的倒数第二行开始向上遍历。对于每一行，我们遍历每一个元素，将它更新为它自身加上它下一行的两个相邻元素中的较大者。这样，每个元素都会变成从它开始到底部的最大路径的和。 当我们到达三角形的顶部时，triangle[0][0]就是我们要找的最大路径的和 代码 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 use std::io::stdin;use std::cmp::max;fn read_vector () -> Vec <i32 > { let mut str = String ::new (); stdin ().read_line (&mut str ).unwrap (); str .split_whitespace () .map (|s| s.trim ().parse::<i32 >().unwrap_or (0 )) .collect () } fn main () { let n = read_vector ()[0 ] as usize ; let mut triangle : Vec <Vec <i32 >> = Vec ::new (); for _ in 0 ..n { triangle.push (read_vector ()); } for i in (0 ..n-1 ).rev () { for j in 0 ..=i { triangle[i][j] = max ( *triangle.get (i + 1 ).and_then (|row| row.get (j)).unwrap_or (&0 ), *triangle.get (i + 1 ).and_then (|row| row.get (j + 1 )).unwrap_or (&0 ), ); } } println! ("{}" , triangle[0 ][0 ]); }
题目链接
思路 将题目抽象成模型: 最长不升子序列和最长上升子序列
求解最长不升子序列。我们使用动态规划的方法，dp[i]表示以第i个导弹为结尾的最长不升子序列的长度。对于每一个导弹，我们都检查在它之前的所有导弹，如果某个导弹的高度大于或等于它，那么我们就可以选择在这个导弹之后发射当前的导弹，所以dp[i]就可以更新为dp[j] + 1（其中arr[j] >= arr[i]）。我们用一个变量ans来记录最长不升子序列的长度，每次更新dp[i]的时候，都用它来更新ans。
求最长上升子序列。我们还是使用动态规划的方法，dp[i]表示以第i个导弹为结尾的最长上升子序列的长度。对于每一个导弹，我们都检查在它之前的所有导弹，如果某个导弹的高度小于它，那么我们就可以选择在这个导弹之后发射当前的导弹，所以dp[i]就可以更新为dp[j] + 1（其中arr[j] < arr[i]）。我们用一个变量ans来记录最长上升子序列的长度，每次更新dp[i]的时候，都用它来更新ans。
代码 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 55 56 #include <bits/stdc++.h> using namespace std;const int maxn = 100050 ;int arr[maxn], dp[maxn], s[maxn], n = 0 , k, ans;void SearchAnswer (bool isGreater) for (int i = 1 ; i <= n; ++i) { dp[i] = 1 ; int left = 0 , right = ans + 1 ; while (right - left > 1 ) { int mid = (left + right) >> 1 ; if (isGreater) { if (s[mid] >= arr[i]) { left = mid; } else { right = mid; } } else { if (s[mid] < arr[i]) { left = mid; } else { right = mid; } } } dp[i] = left + 1 ; s[dp[i]] = arr[i]; ans = max (ans, dp[i]); } } int main () ios::sync_with_stdio (0 ); while (cin >> k) arr[++n] = k; SearchAnswer (true ); cout << ans << endl; ans = 0 ; memset (s, 0 , sizeof (s)); SearchAnswer (false ); cout << ans << endl; return 0 ; }
博客仓库 Cai1Hsu/blog
