此题非常好！！！ 思路：基础取数 dp 的变式。  考虑只能向下走和向右走（很简单） 考虑只能向上走和向右走（很简单） 区别：既可以向上走又可以向下走 所以我们考虑对于每一列，既进行向下的 dp 也进行向上的 dp （具体过程见代码）   #include <bits/stdc++.h> using namespace std; #define ll long long #define mem2(p, x) memset(p, x, sizeof(p)) const int N = 1009; int n, m, a[N][N]; ll dp[N][N], fu1[N], fu2[...

双指针模板题。思路：  其实没什么好说的，这题都讲烂了，无非是维护两个指针 l，r 来标识前后位置，维护 sum 代表其间的和，若 sum 大于等于 x 就尝试更新答案并移动左指针，若 sum 小于 x 就移动右指针（指针都只向前移动，移动时保证 sum 为 l，r 之间的和） 唯一的麻烦在于边界处理，建议一边想一边写，这样能更方便快速的得出结论  #include <bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long typedef pair<int,...

算法进阶指南 例题 改编。思路（来自 算法进阶指南 一书）：  假设我们只有两行 a，b 需要被合成 排序 最大值显然是 a[n] + b[n] ，记录最大值 次大值可能出现在 a[n - 1] + b[n] 和 a[n] + b[n - 1] 之中 ……（自己写两个数组同上分析） 我们发现，对于任意的 a[x] + b[y] 若其没有被取走那么：所有的 yy < y ，a[x] + b[yy] 必不可能是当前形势下的最大值（对 x 的分析相同） 也就是说对于任意的 a[x] + b[y] 若其被取走，那么就会解锁 a[x - 1] + b[y] 和 a[x] + b[y - 1] 而我...

思路：  代数法分析 对于每一种变化，我们可以用代数的方法将其表示出来 第一种变化：a[i][j] --> a[n - i + 1][n - j + 1] 第二种变化：a[i][j] --> a[n - i + 1][j]  最有意思的在于我们如果尝试对翻转的再翻转或者镜像的再镜像，其 i，j 的位置是会复原的（废话） 于是我们知道 x --> n - x + 1 这个变化是自反的（通过两次这样的变化其值又会变回 x ）   所以最后的解法：考虑使得 i，j 变成 n - x + 1 形式的操作次数，若发生偶数次则当作无事发生，否则就进行相对应的变换。  #include &...

思路：  dp 我们枚举每一位变成每一种字符（26种）时的花费（保证此时字符串递增）。   值得注意的是当我们计算花费时需要取得当前位最小值，就必须要去遍历前面状态小于自己字符的花费取最小，这个问题可以通过加一个额外的记录最小值的变量完成，不过在代码里我们做的更绝：每一位保存的都是全体最小值，其意义为：当前位置取不大于当前字符的字符时的最小花费。这样问题就解决了。 #include <bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define intm...

思路：  类似于 算法竞赛进阶指南 中的例题 最短Hamilton路径 ，只是多了一个”跳跃“的属性 对于原例题，我们采取 状压dp 的思路来求得以每一个状态结束时的最优解 有两维：当前选取值（二进制串）、当前所在位置  对于本题，我们考虑分层图的思路（记录一个类似的状态）也就是记录当前跳跃了几次。  #include <bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long typedef pair<int, int> pii; typedef pa...

思路一：  在保证最长上升子序列的前提下修改数最少：等价于求最长上升子序列长度  #include <bits/stdc++.h> const int N = 1000009; int n; string s; int qu[N], tot; int finding(int x) { /// 二分加速 int l = 1, r = tot; while(l < r) { int mid = l + r >> 1; if(qu[mid] > x) r = mid; else l = mid + 1; } return l; } int main() { cin...

思路一：直接记忆化搜索（遇见不会的 dp 先记忆化搜索了再说（记忆化过不了就是需要优化）） #include <bits stdc++.h> using namespace std; int n, m; vector<pii> ve[69]; int dp[100][42009], vis[100][42009]; int dfs(int x, int s) { if(s < 0) return intmax + 1; if(x > m) return 0; if(vis[x][s] ++) return dp[x][s]; /// 防止进入...

题解思路：参考楼下大佬的思路：是否有和最后一个next[]相同的next值在数组中间出现，若存在最后一个next就是答案。否则，next[最后一个next]才是解（当然，特判解不存在）。 这里重点贴一下代码，其中未注释代码为从 0 开始的 next 数组求解，注释的代码则是从 1 开始的 next 数组求解（注释的代码也是AC代码）。 代码中 next 存储的是指定位置最长前缀的长度（不是位置）。 #include <bits/stdc++.h> using namespace std; #define ll long long const int N = 1000009; str...

本题思路来源：AC大佬代码。      思路：           枚举中转点，那么最长的路就是以中转点为起点的最短路中最长的两条的和。      #include <bits/stdc++.h> using namespace std; #define ll long long typedef pair<int, int> pii; const int mod = 1e4; con...

拿个沙发此题是典型的思维题，且 “思维容易，实现难” 主要是实现比较难想到。 代码如下，具体细节通过注释给出其中，c 数组记录选中数在 a 中的下标，d 数组记录选中数的值，c 和 d 的配合可以对选出来的离散集合进行排序，通过排序后的结果，依次修改 a 数组和 b 数组。 #include <iostream> #include <algorithm> #include <vector> #include <cstring> using namespace std; int a[100009], b[100009], n; int c[1000...