maximum balanced circle-编程思维

here 首先根据题意,我们不难有数字是连续的这种感悟。 而且限制是值域上的,从下标入手发现难以突破,便从值域上入手。 从小到大考虑每个数字,然后dp,可以参考这篇题解。 至于方案的输出,有两种情况。 只有自己\(i\)和\(i-1\),直接输出即可。 有自己和\(i-1\)的环,定义print输出环,且最大值全部集中在左侧,那么在递归时只需将\(cnt[i-1]\)减1后调用print(i

线性dp-编程思维

P2285 [HNOI2004]打鼹鼠 这道题目类似最长上升子序列 这是一道线性dp的题目 怎么设置状态呢? f[i]:表示最后一只鼹鼠选择i的最大值 转移:f[i] = max(f[i], f[j] + 1) #include <bits/stdc++.h> using namespace std; const int N = 1e4 + 10; int f[N]; st

树的直径-编程思维

树的直径 树中两点之间的距离:连接两点的路径上的权值之和 树的直径:树中最远的两个节点之间的距离 树的直径的两种求法,一种是两边bfs or dfs,一种是树形dp 直径的性质 1、直径两端点一定是两个叶子节点 2、距离任意点最远的点一定是直径的一个端点,这个基于贪心求直径方法的正确性可以得出 bfs做法 例题大臣的旅费 #include <iostream> #includ

关于长链剖分的数组实现 | cf1009f dominant indices-编程思维

请容许我不理解一下为什么这题题解几乎全都是指针实现/kk 其实长链剖分是可以直接用数组来写的。 考虑朴素 DP。设 \(f_{u,i}\) 表示以点 \(u\) 为根的子树中与点 \(u\) 距离为 \(i\) 的点的个数。 则转移方程为: \[f_{u,i}=\sum\limits_{v\in son_u} f_{v,i-1} \]答案为: \[ans_u=\max\{f_{u,i}\} \]

ybtoj 数位dp g.幸运666-编程思维

日常写点奇奇怪怪的乱搞做法 awa 这题跟前面几道数位 DP 的区别在于让求第 \(n\) 小的数。 虽然我不会求也不想学这个,但我们可以 binary search! 问题就转换为求 \([1,mid]\) 中的幸运数个数,这样就和前面那些题做法一样了/xyx code #include<bits/stdc++.h> #define int long long using nam

树上问题学习笔记-编程思维

前言:这篇博客是 yx NOIP 前恶补知识点写的,并没有普通树形 DP 捏/wq upd:NOIP 没了,现在这里有普通树形 DP 了( 换根 DP gg 押 NOIP 会考换根 DP,发现自己还没学过/jk 害怕.jpg 或许按本人感受的难度顺序排序(? P3478 [POI2008] STA-Station 当根从 \(u\) 换到 \(v\) 时,\(v\) 的子树内所有节点深度 \(-

dp 杂题选做-编程思维

部分详见: 概率期望 DP 学习笔记 树形 DP 学习笔记 其余题就不具体分类了。 P1220 关路灯 题解说这是区间 DP 经典题,但我以前居然没听说过,这下尴尬了。 设 \(f_{i,j,0/1}\) 表示关掉区间 \([i,j]\) 所有灯,人在点 \(i/j\) 消耗的最少功率。 那么 \[f_{i,j,0}=\min(f_{i+1,j,0}+dis_{i,i+1}\times (su

乘号加号-编程思维

感觉还是不太明白它 std 给的那个循环边界问题呜呜呜 (但我认为我这样写似乎并没有问题...... 设 f[i][j] 表示在前 i 个数中使用 j 次乘法后的最大答案。 所以就是  f[i][j]=max(f[i][j],f[k][j-1]*(sum[i]-sum[k]));  由于要求区间的和,所以使用前缀和优化。 sum 数组即前缀和数组。 #include<bits/stdc+

采药(lgp1048)-编程思维

emmm 01 背包模板... 设 f[i] 表示背包容积为 i 时所得的最大价值。 则状态转移方程为 f[j] = f[j - w[i]] + c[i] 。 #include<bits/stdc++.h> using namespace std; int w[1001],c[1001],t,m,f[1001]; int main() { scanf("%d%d",&

最长公共子序列-编程思维

用时 10min ,一遍过。 设 f[i][j] 表示第一个字符串的前 i 位和第二个字符串的前 j 位最长公共子序列的长度。 当比较的这两个字母相同时,f[i][j] = f[i-1][j-1] + 1 。 否则 f[i][j] = max(f[i-1][j],f[i][j-1]) 。 #include<bits/stdc++.h> using namespace std; ch

合唱队形(lgp1091)-编程思维

思路: 先从左到右求一遍最长不下降子序列,再同样方法从右到左求一遍。 然后我们枚举分界点,则总人数就是左边一半加上右边一半的人数。 取最大值,输出答案。 见注释。 #include<bits/stdc++.h> using namespace std; int n,a[101],f1[101],f2[101],ans; int main() { cin>>n;

严格递增序列-编程思维

 想了很久没想出来,无奈之下看了题解。 如果 a[i] < a[j] ,因为要保证都是整数,所以 j - i 必须要小于 a[j] - a[i] ,才能使区间 i,j 内的所有数均可修改。 j - i < a[j] - a[i] 移项得 a[i] - i < a[j] - j。 所以 a[i] 里要存 a[i] - i 的值,则求出最长不下降子序列后就可以保证其中的数都能够修改

cf963b destruction of a tree 题解-编程思维

CF963B Destruction of a Tree 题解   洛谷题目链接   这里提供一个较为朴素的 DP 想法。 题意简述   给定一棵树,节点个数不超过 \(2 \times 10^5\),每次可以删掉度数为偶数的点。问最后能不能删完;能删完给出删除方案。 思路分析   首先可以随便选一个点作为根。   其次,我们考虑在一棵子树的删除情况,我们令根节点为 \(u\),它的直接儿子为

solution -「arc 106e」medals-编程思维

Desc.   Link.   你有 \(n\) 个朋友,他们会来你家玩,第 \(i\) 个人 \(1...A_i\) 天来玩,然后 \(A_i+1...2A_i\) 天不来,然后 \(2A_i+1...3A_i\) 又会来,以此类推;   每天你会选一个来玩的人,给他颁个奖,如果没人来玩,你就不颁奖。   你要给每个人都颁 \(K\) 个奖,问至少需要多少天。 Sol.   前面的部分很套

solution -「hdu」ridiculous netizens-编程思维

Desc.   给定一棵 \(N\) 个节点无根树,找出满足以下条件的集合 \(S\) 的数量: \(S \subseteq \{1,\dots,n\}\); \(S\) 的导出子图联通; \(\displaystyle\prod_{v \in S} a_v \leqslant M\)。 Sol.   点分治,统计包括当前分治中心的集合数量,如果从子树的角度入手会发现并不好做——合并这一步就

「codeforces-编程思维

link。 一个 dp(拜谢 ly)和切入点都略有不同的做法,并不需要观察啥性质。 原问题针对子序列进行规划,自然地想到转而对前缀进行规划。接下来我们考虑一个前缀 \([1, i]\) 以及一个 \(j \in [1, i]\) 对答案的贡献,可以写出 \(\displaystyle \textit{cont}(j \text{ to } [1, i]) = [\max_{i < k} a

「codeforces-编程思维

link。 首先考虑暴力,枚举规划前缀 \([1, i]\) 和前缀 mex \(x\),则我们需要 \(x\) 个数来填了 \([0, x)\),还剩下 \(i-x\) 个数随便填 \([0, x) \cup (x, n]\),如果直接组合数算可能会出问题,考虑 dp。 定义 \(f[i][x][j]\) 表示规划前缀 \([1, i]\),当前的 mex 为 \(x\),还有 \(j\) 个

「codeforces-编程思维

link。 考虑把原问题写成一个在 \(\left(\log_2 \max v \right) \times n\) 的矩阵里选出三列,我们首先预处理出 \(j \cap q\)。具体,我们需要对于每一个权值 \(v\) 求出一个最大的下标 \(p\)(\(1 \leqslant p \leqslant n\))满足存在极大的 \(q < p\) 且 \(v \cap a_p \cap a

zxy 简单 dp 大讲堂-编程思维

讲课讲得非常清楚啊,我绝赞膜拜。节奏可以,思路清晰,解法自然,为讲师点赞。 第一个题是 loj3282 / joisc2020 - Treatment Project。原问题由 \(\left(S, t, w\right)\) 三个维度构成,分别表示村民被治疗的状态,时间,花费。比较自然的思路是针对 \(t\) 做规划,但是这样有一个问题——\(t\) 和 \(S\) 是息息相关的,若从 \(t