#include <iostream> #include <cstring> using namespace std; const int N = 1e5 + 10; int n; int e[N * 2], ne[N * 2], h[N], idx; // sons[i] 记录节点i为根的子树的节点数 int sons[N]; // 记录节点的颜色 int colors[N]; bool isFailed = false; // 是否染色失败 void add(int a, int b) { e[idx] = b; ne[idx] = h[a]; ...

思路 对于二叉树种任一节点k，如果k作为某个路径上的一个点，这个路径的方向分两个方向： 1） 从节点k到k的父节点的方向。因为k的父节点dfs(par(k)))需要用到dfs(k)，需要返回这个方向上的值，需要从k的左右子树中选择大的(要和0比较，贪心)那个子树再加上val(k) 2） 不到k的父节点，也就是说路径在以k为根节点的子树中，计算路径和 3） 从情况1和情况2中去最大值更新答案 维护一个答案ans，保存最大路径和。给dfs根节点的编号1，一遍dfs之后ans就是答案 #include <iostream> #include <vector> using n...

遍历每个颜色red[i]: 如果red[i]=1 (R)：将自身以及它的父节点，以及父节点的父节点... 让他们的cnt[父->父]++ 每次询问直接输出cnt[q]即可 #include <iostream> #include <cstring> using namespace std; const int N = 1e5+10; int par[N]; int red[N]; int cnt[N]; int n; int main() { cin >> n; int p; memset(par, -1, sizeof(pa...

树状dp，一般需要遍历树。方式是深度遍历。 这个题，节点用输入数值的下标来表示，如图所示： f[i][0]表示 以i为根的子树，并且不包括节点i（最大值不包括节点的值）的最大值，该状态可以来自于左右子树（如果存在）的max(f[左子树][0], f[左子树][1])+max(f[右子树][0], f[右子树][1]) f[i][1]表示 以i为根的子树，并且包括节点i（最大值包括节点的值）的最大值，该状态可以来自于f[左子树][0]+f[右子树][0]+a[i] #include <iostream> #include <cstring> using namespa...

#include <iostream> #include <cstring> using namespace std; const int N = 55; const int M = 110; int n; char a[N]; char b[N]; int dp[N][N][N][N]; int main() { cin >> n; for (int i = 0; i < n; i++) { cin >> a + 1 >> b + 1; int lena = strlen(a +...

#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 30; int n; int w[N]; int f[N][N], g[N][N]; void print(int l, int r){ if(l > r) return; int root = g[l][r]; cout << root << " &q...

题解 定义dp[i][j]是区间str[i~j]上的最少涂色次数。 区间dp的核心思想是由一个个小区间合并成大区间， 所在在dp时应该从长度最短的区间考虑，就是长度为1的区间。 1.长度为1的区间 涂色次数为1 2.长度为2的区间 它可以由两个长度为1的区间合并，这个题的特殊地方在于一次可以涂一个连续区间。所以： 如果str[i]=str[j]，那这个长度为2的区间[i~j]只需要涂一次。 如果不同，就是两个区间次数相加了（2次） 3.长度为len的区间 仿照区间长度为2的时候，可以枚举区间中的某个分割点来进行分割，并且题目要求可以一次涂一整个区间，所以： str[i]==str[j]: d...

区间dp dp[i][j]: 区间[i~j]的字符串匹配所插入的字符数最少为dp[i][j] 区间dp，枚举区间长度来遍历i和j。 初始时，区间长度为1时，dp[i][i]=1。长度不为1时，dp[i][j] = inf 当s[i]和s[j]匹配时，dp[i][j] = dp[i+1][j-1] 然后就是枚举区间[i~j]内的分界点，看区间划分的左右两部分的匹配数 #include <iostream> #include <string.h> using namespace std; const int N = 101, inf = 0x3f3f3f3f; char...

#include <iostream> using namespace std; const int N = 2*1e4+10; int dp[N]; //dp[k]表示容量为v时，最大能装多大体积的物品 int nums[31]; int main() { int v,n; scanf("%d", &v); scanf("%d", &n); for(int i = 1; i <= n; i++){ scanf("%d", &nums[i]);...

思路转移：从一个数组中取数字，每个数字只能取一次，问取出的数字之和与未取出的数字之和能否相等。 分析：一个数组中的所有数字分为两部分，问两部分的和能否相等，很明显，如果整个数组的和(s)是奇数，必然不能。当为偶数，则判断是否能在数组中取出一些数，使得它们的和为s/2。 这样问题转移为：容量为s/2的背包，nums保存多个物品的重量，每个物品仅有一个，问能否把背包装满？ dp[i]表示 当容量为i时，背包能最多装多重的物品。答案就是dp[s/2]==s/2，当容量为s/2时，看最大能装重量是否是s/2? 转移：dp[j] = max(dp[j], dp[j-nums[i]]+nums[i])，当...

解释下这种状态转移的思路： dp[i]表示组成i的最少货币数，那对于一种状态dp[k]，就表示组成k的最少货币数状态，它可以来自于两个方面： 遍历每个货币，当k>=arr[i]就可以来自于dp[k-arr[i]]这个状态，表示组成{k-arr[i]}的最少货币数再加上arr[i]这种货币1个就到了dp[k]； 上面那种状态的计算的值比本来自己的值（最少货币数）还大，就不更新了，保持原状态。 至于想象中是否需要考虑每种货币的数量，其实在更新较小的状态时就保存了数量的信息。 比如arr={2,5}, aim = 6, dp[6]可以来自dp[4]和dp[1]（一定是INT_MAX）, dp...

动态规划：dp[i]表示正整数i最少能由多少个完全平方数组成，答案dp[n]初始化dp[N]=INT_MAX，dp[0]=0转移方程：dp[i+j*j] = min(dp[i+j*j] , dp[i]+1)数字x最少组成个数来自自己本身，或者数i，并且i满足：x=i+j*j #include <iostream> #include <cmath> #include <climits> using namespace std; const int N = 10010; int dp[N]; // dp[i]表示正整数i最少能由多少个完全平方数组成，答案dp[...

dp[i][j] 表示前i个数字中取出的数的和，并且对k取余为j的最大值，答案就是dp[n][0]，表示对k取余为0的最大和。 整个dp初始化为-1： memset(dp, -1, sizeof(dp)) dp[0][0]初始化为0，表示前0个数取出的数的和是k的倍数的最大值为0； 1、 不取a[i]这个数的情况：当dp[i-1][j]!=-1，dp[i][j]=dp[i-1][j]； 2. 取a[i]：可以这样想，加上a[i]会导致dp[i][j]所有数的和对k取余有k种情况，所以枚举所有情况。dp[i][j] = dp[i-1][((j-a[i]%k)+k)%k]+a[i]和dp[i][...

#include <cstdio> #include <iostream> #include <queue> using namespace std; const int N = 510; int dp[N][N]; int n, m; int main() { scanf("%d%d", &n, &m); char tmp; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { ...