动态规划，复习

一.动态规划 1.

思路：每次递增序列结束都取最优解

class Solution { public: int findLengthOfLCIS(vector<int>& nums) { int ans = -1,temp = 1; for(int i = 0;i<nums.size()-1;i++){ if(nums[i]<nums[i+1]) temp++; else{ ans = max(ans,temp); temp = 1; } } ans = max(ans,temp); return ans; } };  2.

思路：动态规划五部曲

/* dp[i]表示以i为结尾的最长子序列的长度 递推公式为前i项的哪个有最大子序列长度，哪个就是dp[i]=max(dp[i],dp[j]+1) 初始化为每个长度都为1； 前到后 */ class Solution { public: int lengthOfLIS(vector<int>& nums) { vector<int>dp(nums.size()+1,1); for(int i = 0;i<nums.size();i++){ for(int j = 0;j<i;j++){ if(nums[i]>nums[j]) dp[i] = max(dp[j]+1,dp[i]); } } return ranges::max(dp); } };  3./

思路：动规五部曲

/* dp[i][j]表示为nums1前i-1项，和nums2前j-1项最大的重复子集dp[i][j]; dp[i][j] = dp[i-1][j-1]+1 初始化都为0 */ class Solution { public: int findLength(vector<int>& nums1, vector<int>& nums2) { vector<vector<int>> dp (nums1.size() + 1, vector<int>(nums2.size() + 1, 0)); int result = 0; for (int i = 1; i <= nums1.size(); i++) { for (int j = 1; j <= nums2.size(); j++) { if (nums1[i - 1] == nums2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } if (dp[i][j] > result) result = dp[i][j]; } } return result; } };  4.

思路：动规五部曲

 

/* dp[i][j]表示为text1前i-1项和text2的前j-1项的最大公共子序列长度 递推公式：dp[i][j] = dp[i-1][j-1]+1 初始化为0 */ class Solution { public: int longestCommonSubsequence(string text1, string text2) { vector<vector<int>>dp(text1.size()+1,vector<int>(text2.size()+1,0)); for(int i = 1; i <= text1.size(); i++){ for(int j = 1; j <= text2.size(); j++){ if(text1[i-1]==text2[j-1]) dp[i][j] = dp[i-1][j-1]+1; else dp[i][j] = max(dp[i-1][j],dp[i][j-1]); } } return dp[text1.size()][text2.size()]; } }; 二.回顾 1. 埃拉托斯特尼筛法 #include <iostream> #include <vector> using namespace std; const int MAX_N = 100000000; // n 的最大值为 10^8 // 埃拉托斯特尼筛法 void sieve_of_eratosthenes(int n, vector<int>& primes) { vector<bool> is_prime(n + 1, true); // 默认所有数是素数 is_prime[0] = is_prime[1] = false; // 0 和 1 不是素数 for (int i = 2; i * i <= n; ++i) { if (is_prime[i]) { for (int j = i * i; j <= n; j += i) { is_prime[j] = false; } } } // 收集所有素数 for (int i = 2; i <= n; ++i) { if (is_prime[i]) { primes.push_back(i); } } } int main() { ios::sync_with_stdio(0); // 加速 cin 和 cout int n, q; cin >> n >> q; // 找到小于等于 n 的所有素数 vector<int> primes; sieve_of_eratosthenes(n, primes); // 处理每个查询 while (q--) { int k; cin >> k; cout << primes[k - 1] << endl; // 输出第 k 小的素数 } return 0; } 2.二分

思路：二分答案加贪心

class Solution { public: int splitArray(vector<int>& nums, int k) { int l = 0,r= 0; for(int t:nums) r +=t; int ans = 0; while(l<=r){ int mid = (r+l)>>1; if(check(nums,mid,k)){ ans = mid; r = mid-1; }else l = mid+1; } return ans; } bool check(vector<int>& nums,int mid,int k){ int sum = 0; int count = 1; for(int i = 0;i<nums.size();i++){ if(nums[i]>mid)return false; sum+=nums[i]; if(sum>mid){ count++; sum = nums[i]; if(count>k)return false; } } return true; } }; 3.二分 

思路：二分答案模板题

#include <stack> #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <climits> #include <cstdlib> #include <cmath> #include <unordered_set> #include <unordered_map> #include <map> #include <set> #include <cctype> using namespace std; const int MAXN = 50001; int stone[MAXN], a, n, m; bool check(int d) { int p = 0, ans = 0; for (int i = 1; i <= n; i++) { if (stone[i] - p < d) ans++; else p = stone[i]; } if (ans <= m) return true; else return false; } int main() { scanf("%d %d %d", &a, &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &stone[i]); stone[++n] = a; int l = 0, r = a, mid; while (l < r) { mid = (l + r + 1) / 2; if (check(mid)) l = mid; else r = mid - 1; } printf("%d\n", l); return 0; } 4.卡特兰数

#include <stack> #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <climits> #include <cstdlib> #include <cmath> #include <unordered_set> #include <unordered_map> #include <map> #include <set> #include <cctype> using namespace std; int main() { int n; cin >> n; long long dp[10000]; dp[0] = 1; dp[1] = 1; for (int i = 2; i <= 2 * n + 1; i++) { dp[i] = i * dp[i - 1]; } cout << dp[2 * n] / (dp[n] * dp[n] * (n + 1)); return 0; }  三.算阶 1.

思路：单调栈

#include <stack> #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <climits> #include <cstdlib> #include <cmath> #include <unordered_set> #include <unordered_map> #include <map> #include <set> #include <cctype> using namespace std; int main() { int n; while (cin >> n && n != 0) { vector<long long>arr(n + 2,0); for (int i = 1; i <= n; i++) cin >> arr[i]; long long stk[100005], top = 0; long long ans = INT_MIN; for (int i = 0; i <= n + 1; i++) { while (top && arr[stk[top]] > arr[i]) { int cur = stk[top--]; int high = arr[cur]; int weihgt = i - stk[top] - 1; ans = ans > high * weihgt ? ans : high * weihgt; } stk[++top] = i; } cout << ans << endl; } return 0; }  四.分治 1.

思路：归并排序的思想加上分治，先左边，在右边，在跨左右计算小和

#include <stack> #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <climits> #include <cstdlib> #include <cmath> #include <unordered_set> #include <unordered_map> #include <map> #include <set> #include <cctype> using namespace std; const int N = 100005; long long arr[N], help[N]; int n; long long merge(int l, int mid, int r) { long long sum = 0, ans = 0; for (int i = l, j = mid + 1, sum = 0; j <= r; j++) { while (arr[i] <= arr[j] && i <= mid) sum += arr[i++]; ans += sum; } int i = l; int a = l; int b = mid + 1; while (a <= mid && b <= r) help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++]; while (a <= mid) help[i++] = arr[a++]; while (b <= r) help[i++] = arr[b++]; for (int i = l; i <= r; i++) arr[i] = help[i]; return ans; } long long small(int l, int r) { if (l == r)return 0; int mid = (l + r) / 2; return small(l, mid) + small(mid + 1, r) + merge(l, mid, r); } int main() { cin >> n; for (int i = 0; i < n; i++) cin >> arr[i]; cout << small(0, n - 1); return 0; }