一.动态规划
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;elsedp[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 和 coutint 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;}elsel = 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;
}
