假设两个字符串分别是a和b。dp[i][j]表示 所有将a[1~i]变成 b[1~j]的操作方式的最少次数。对于状态dp[i][j]可以怎么划分呢？从三个操作的角度考虑：1） 删除操作：a的[1~i-1]==b的[1~j]，删除a中第i个字符，a[1~i]和b[1~j]就变成一样了==》f[i][j] = f[i-1][j]+1。2) 添加操作：a的[1~i]==b的[1~j-1]，添加b[j]作为a中第i个字符，a[1~i]和b[1~j]就变成一样了==》f[i][j] = f[i][j-1]+1。3） 修改操作： 3.1） 当前若有 a[i]==b[j]：不需要修改， ==》 f...

设dp[i][j]表示 1~i的s1子串和1~j的s2子串的最长公共子序列的最大长度思想：从哪里来如果s1[i]==s2[j]了，那这个f[i][j] = max(f[i][j], f[i-1][j-1]+1)如果s1[i]!=s2[j]f[i][j] <-- max( f[i-1][j], f[i][j-1], f[i][j]) #include <cstdio> #include <iostream> #include <cstring> using namespace std; const int N = 1010; int dp[N][N]...

按照长度从小到大排序，当长度相同时，按照宽度从大到小排序。在宽度的维度上，动态规划求最长上升子序列的长度为什么能这么做呢？首先，宽度的维度上，动态规划求最长上升子序列 在长度方向上肯定也是 从小到大的。这里面不存在相等的长度，因为本身上升子序列是一种递增的顺序，而如果长度相同了，它的对应的宽度是第减的（当长度相同时，按照宽度从大到小排序）。这样就严格保证了 两边都是严格小于的 #include <iostream> #include <vector> #include <algorithm> using namespace std; typedef pair...

关键找 第i个，1~i 是一种递增的顺序， i~k是递减的顺序最少几位出列： 找一个i 使得递增序列的长度和递减序列的长度 和最大那就枚举 每个i 作为那个 队形中 最高值的情况。这样i之前就是 求以h[i]为结尾的最长递增子序列的长度，就是求一遍数组的最长子序列，对应的f[i]自然就表示了“h[i]为结尾的最长递增子序列的长度” #include <iostream> using namespace std; const int N = 1000; int h[N]; int f[N]; //f[i]表示 以i为结尾的 最长上升子序列的长度 int g[N]; //g[i]...

等价于求两个问题：问题1： 求最长不增（小于等于）子序列的长度方面就是 线性dp问题2： 求 最少可以划分出不增（小于等于）子序列的个数 #include <iostream> #include <set> using namespace std; const int N = 1010; int h[N]; int dp[N]; //dp[i]表示 长度为i的 子数组的 最长不增（小于等于）子序列的长度。 int main() { int n; cin >> n; for(int i = 1;i<=n;i++){...

#include <iostream> #include <cstring> using namespace std; int dp[1010]; int main() { int n; cin >> n; int arr[n]; for(int i = 1;i<=n;i++){ cin >> arr[i]; dp[i] = 1; } long long res = 0; for(int i = 1;i<=n;i++){ for(...

#include <iostream> #include <cstring> using namespace std; const int N = 501; int map[N][N]; int dp[N][N]; //其中 dp[i][j]表示 到位置(i,j)时的最小路径和 int main() { int n, m; for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { dp[i][j] = 500000; }...

#include <climits> #include <cstdio> #include <iostream> #include <string.h> using namespace std; const int N = 105; int map[N][N]; int pre_j[N][N]; //pre_j[i][j]表示 固定在j这一列中，的前缀和 int main() { int n; scanf("%d",&n); for(int i = 1;i<=n;i++){ for(in...

#include <iostream> using namespace std; const int N = 200010; int dp[N]; //dp[i] 表示数组 1~i满足的最大值 int a[N]; int main() { int n; scanf("%d",&n); for(int i = 1;i<=n;i++) scanf("%d", &a[i]); //连续的子序列， 连续。。。 int res = -1e9; dp[1] = a[1]; res = dp[1]; ...

#include <iostream> using namespace std; const int N = 100010; int costs[N]; int dp[N]; int main() { int n; cin >> n; for(int i = 0;i<n;i++){ scanf("%d", &costs[i]); } //最小花费--从哪里来 //对于台阶1来说，可以来自自己， dp[1] = min(dp[0]+costs[0], 0); dp[1] = min(d...

#include <cstdio> #include <iostream> #include <algorithm> #include <cmath> using namespace std; int main() { int n; scanf("%d", &n); int dp[21] = {0}; dp[0] = 1; dp[1] = 1; //dp[i]满足公比为2的 等比数列 printf("%d",(int)pow(2,n-1)); return 0; } /...

#include <iostream> #include <string> #include <sstream> #include <vector> #include <bitset> using namespace std; int isSub(string sub) { //判断子网掩码是否正确 stringstream ss(sub); string t; int first_1 = 0; int first_0 = 0; while (getline(ss, t, '.'))...

#include <cctype> #include <iostream> #include <string> using namespace std; int main() { string s; cin >> s; string::iterator it = s.end(); long long ans=0; long long cnt = 1; while (*(--it)!='x') { char c = *(it); if(isdigit(c)){ ...

将数组a中的数字变成和数组b中的数字顺序一样（两个序列都是由相同的无重复数字集合组成的），可以通过将每个唯一的数字映射到唯一的下标上。目标数组b中，记b[pos1]=b1,b[pos2]=b2,...,b[posj]=bj,...,b[posn]=bnb[pos_1]= b_1,b[pos_2]= b_2,...,b[pos_j]= b_j,...,b[pos_n]=b_nb[pos1​]=b1​,b[pos2​]=b2​,...,b[posj​]=bj​,...,b[posn​]=bn​，将数组a中对应的值（a[i]=b[j]）修改为a[i]=posja[i]=pos_ja[i]=posj​...