#include <iostream> #include<cstring> using namespace std; const int N = 100010; int a[N], f[N]; int jump(int n){ if(n == 0) return -1; if(n == 1) return a[0]; f[0] = a[0]; for(int i = 0; i < n; i ++){ if(f[i] != -1){ int maxReach = min(n - 1, i ...

贪心算法 #include <iostream> using namespace std; const int N = 2 * 100010; int a[N]; int main() { int n; cin >> n; for(int i = 0; i < n; i ++) cin >> a[i]; int maxReach = 0; int i; for(i = 0; i < n; i ++){ if(i > maxReach){ cout &...

#include <iostream> using namespace std; const int N = 2 * 100010; int a[N], f[N]; int main() { int n; cin >> n; for(int i = 1; i <= n; i ++) cin >> a[i]; f[1] = a[1]; for(int i = 2; i <= n; i ++){ f[i] = max(f[i - 2] + a[i], f[i - 1]); } ...

f[i][j]为范围从i到j的最长回文子序列当s[i] == s[j]时 f[i + 1][j - 1] + 2当s[i] != s[j]时 max(f[i][j - 1], f[i + 1][j])初始化：当i不断向右移动j不断向左移动，最终会到中间i == j的位置，这个时候是需要初始化 f[i][i] = 1由于 要从i + 1 推出 i 从j - 1推出 j 所以i要-- j要++ 即i从后往前遍历的顺序 而j必须要时刻大于i 因为[i,j]范围 #include <iostream> using namespace std; const int N = 1010; i...

#include <iostream> #include<cstring> using namespace std; int n, m; const int N = 110; int h[N][N]; int f[N][N]; int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; int df(int x, int y){ int &v = f[x][y]; if(v != -1) return v; v = 1; for(int i = 0; i < 4; i ++){ ...

从右往左 求最大递增子序列 从左往右求最大递增子序列合并在一起 去除中间同学 得到山丘型的序列答案 #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 1010; int a[N], f[N], g[N]; int main(){ int n; cin >> n; for(int i = 0; i < n; i ++) cin >> a[i]; for(int i...

根据 Dilworth 定理（一个有序集合的最小链划分数等于最大反链的大小），我们可以知道：最小链划分数：把导弹高度序列划分成若干条递减序列所需的最小数量。最大反链的大小：一个最长上升子序列的长度（因为两个元素不可比较的意思就是：它们可以构成一个递增的关系）可以将序列化分为若干个递减子序列 =》 通过找到最长上升子序列的数量来求解计算最长不增子序列长度（代表最多能拦截的导弹数）。计算最长上升子序列的数量（代表最少需要的拦截系统数）。 #include <algorithm> #include <cstring> #include <functional> #...

#include <iostream> using namespace std; const int N = 510; int a[N][N]; int f[N][N]; int main() { int n, m; cin >> n >> m; for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) cin >> a[i][j]; // 初始化第一列 只能从上方到达 for(int i = ...

#include <iostream> using namespace std; const int N = 100010; int f[N]; int cost[N]; int main() { int n; cin >> n; for(int i = 1; i <= n; i ++) cin >> cost[i]; f[1] = cost[1], f[2] = cost[2]; for(int i = 3; i <= n + 1; i ++){ f[i] = min(f[i - 1] +...

f(n)=f(n−1)+f(n−2)+⋯+f(1)+f(0)f(n - 1) = f(n−2)+⋯+f(1)+f(0)f(n) = 2 * f(n - 1) #include <iostream> using namespace std; const int N = 50; int f[N]; int main() { int n; cin >> n; f[0] = 1; for(int i = 1; i <= n; i ++){ f[i] = f[i - 1] * 2; } cout <&l...

集合：所有A[1-i]、B[1-j]的公共子序列二集合属性：max状态：1. 子序列不包含ai 不包含bj => f[i - 1][j - 1]（去除） 2. 不包含ai 包含bj => f[i - 1][j] 3. 包含ai 不包含bj => f[i][j - 1] 4. 包含ai 包含bj => ...

设dp[i]表示以i为结尾的LIS长度对于每个i都会从0-j进行检查 如果a[i] > a[j]说明i可以接在j后面形成一个更长的上升子序列此时可以更新f[i] = max(f[i], f[j] + 1)初始化：每个元素都是长度为1的序列 #include<iostream> using namespace std; const int N = 1010; int f[N], a[N]; int n; int main(){ cin >> n; for(int i = 1; i <= n; i ++) cin >> a[i]; ...

动态规划dp[i]是以第i个数为结尾的最大和如果加了这个元素 还不如直接选这个元素 呢么就直接选择这个元素 #include <iostream> using namespace std; const int N = 2 * 100010; long long a[N]; long long dp[N]; int main() { int n; cin >> n; long long res = -1e9; for(int i = 0; i < n; i ++) cin >> a[i]; for(int i...

自底向上逐行计算最小路径和 更新当前节点值为底部或底部旁边元素的加和 class Solution { public: int dp[200][200]{0}; int minTrace(vector<vector<int> >& triangle) { int n = triangle.size(); for(int i = n - 2; i >= 0; i --){ for(int j = 0; j < triangle[i].size(); j ++){ ...