https://leetcode-cn.com/problems/maximum-subarray-min-product/submissions/本题先利用单调栈求出数组的元素的边界，再利用前缀和和枚举求解。  class Solution { public: int maxSumMinProduct(vector<int>& nums) { int n = nums.size(); vector<int> left(n, 0); vector<int> right(n, n-1); // vector<long> preSum(n +...

https://leetcode-cn.com/problems/largest-color-value-in-a-directed-graph/submissions/   我自己的解法，记忆化搜索 rec[i]记录以i为起点的路径，所有颜色的最大值  class Solution { public: int n; int idx = 0; vector<int> head; vector<bool> vis1; vector<bool> vis2; struct { int nxt, to; } es[100005]; vector<vector&...

https://leetcode-cn.com/problems/target-sum/solution/yi-tao-kuang-jia-jie-jue-bei-bao-wen-ti-58wvk/   一、目标和 0-1背包的一种变形，原来适用于求最大值，这道题用于求组合数  /* 0-1背包变形 target = x - y; sum = x + y; x = (sum + target) / 2; 用nums中元素组成x，有多少种方法 */ class Solution { public int findTargetSumWays(int[] nums, int target) { in...

https://www.luogu.com.cn/problem/P1352#submit  #include <bits/stdc++.h> using namespace std; const int N = 10005; struct edge { int nxt, to; } edges[N]; int n; int idx; int head[N]; int r[N]; //每个节点的快乐数 int f[N][2]; //f[i][0]为不包含该节点 f[i][1]为包含 inline void add(int a, int b) { edges[++idx].to = ...

力扣完成所有工作的最短时间  class Solution { public: /* @param idx 是jobs序号 */ bool recurse(int limit, int idx, vector<int> &jobs, vector<int> &workers) { if (idx == jobs.size()) { return true; } if (jobs[idx] > limit) { return false; } for (int w = 0; w < workers.size(); ++w) { if (work...

https://blog.csdn.net/yu121380/article/details/81387879  for 所有的组k for v=V..0 for 所有的i属于组k f[v]=max{f[v],f[v-c[i]]+w[i]}

https://www.luogu.com.cn/problem/P2015  #include <bits/stdc++.h> using namespace std; const int N = 205; const int M = 205; struct edge { int nxt, to, w; }edges[M]; int idx; int head[N]; int branch[N]; //记录每个节点的树的树枝数量 int f[N][M]; //f[i][j]是以i为根节点，有j条树枝的树的最优值 int n, q; inline void add(int a, i...

https://leetcode-cn.com/problems/best-meeting-point/  /* 将问题分解成两个子问题，在一维上最近距离是所有点坐标的中位数，那么分别找到 x坐标的中位数和y坐标的中位数就是最佳碰头地点 */ class Solution { public int minTotalDistance(int[][] grid) { List<Integer> rows = new ArrayList<>(); List<Integer> cols = new ArrayList<>(); for (int i = ...

int prime[maxn]; int visit[maxn]; void Prime(){ mem(visit,0); //若为1，则不是素数 mem(prime, 0); //将已经搜索到的素数保存下来 int cnt = 0; //当前有多少个素数 for (int i = 2;i <= maxn; i++) { if (!visit[i]) { prime[cnt++] = i; } for (int j = 0; j < cnt && i*prime[j] <= maxn; j++) { visit[i*prime[j]] = 1; if (i %...

哈利·波特要考试了，他需要你的帮助。这门课学的是用魔咒将一种动物变成另一种动物的本事。例如将猫变成老鼠的魔咒是haha，将老鼠变成鱼的魔咒是hehe等等。反方向变化的魔咒就是简单地将原来的魔咒倒过来念，例如ahah可以将老鼠变成猫。另外，如果想把猫变成鱼，可以通过念一个直接魔咒lalala，也可以将猫变老鼠、老鼠变鱼的魔咒连起来念：hahahehe。 现在哈利·波特的手里有一本教材，里面列出了所有的变形魔咒和能变的动物。老师允许他自己带一只动物去考场，要考察他把这只动物变成任意一只指定动物的本事。于是他来问你：带什么动物去可以让最难变的那种动物（即该动物变为哈利·波特自己带去的动物所需要的魔咒...

给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。 输入格式: 输入首先给出正整数N（≤50），为树中结点总数。下面两行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母（区别大小写）的字符串。 输出格式: 输出为一个整数，即该二叉树的高度。 输入样例: 9 ABDFGHIEC FDHGIBEAC 输出样例: 5 #include<bits/stdc++.h> using namespace std; int dfs(string pre, string in, int n) {  int i = 0; if (n == 0) return 0; els...

非递归汉诺塔问题 #include <bits/stdc++.h> using namespace std; struct _move {  int n; //当前要移动的盘子编号 int u; //上方还有几个盘子 char s, m, d;//起始塔，中间塔，目的塔 _move(int n1, int u1, char s1, char m1, char d1) : n(n1), u(u1), s(s1), m(m1), d(d1) { } }; void honoi(int n, char a, char b, char c) {  if (n <= 0) return...

#include <bits/stdc++.h> using namespace std; using ll = long long; using p = pair<ll, int>; const int maxn = 2e5 + 10; int cnt = -1; int head[maxn]; ll dis[maxn]; bool visted[maxn]; struct Edge{ int to, next, wt; }edges[maxn]; void add(int u, int v, int w) { edges[++cnt].to = v; edges[c...

kmp算法的关键就是前缀和后缀  #include<cstdio> #include<algorithm> #include<cstring> #include<iostream> using namespace std; const int MAX_LEN = 1e5 + 10; int n, len1, len2; char t[MAX_LEN], p[MAX_LEN]; int _next[MAX_LEN]; inline void get_next() {  int i = 0, j; _next[0] = j = -1; while (...