根据题意可以知道叶子结点必须要和他的父亲节点颜色相同，不是叶子节点的节点，而且还没有染色，也让他们和它的父亲同色，如果此时他的父亲已经染过色了那么他就没办法染色了，如果根节点孤寡，也不能染色。 #include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; int tot,n; struct node{ int t; int next; }edage[maxn<<1]; int head[maxn]; void addedage(int x,int y){ edage[++tot].t=y; eda...

解法一：设dp[i]表示长度为i的合法字符串dp[i]的状态转移有两种一：长度为i-1的合法的字符串数量在这种情况中第i位随便填一个字母就可以了即26dp[i-1]二：长度为 i-1的包含u但不包含us的字符串的数量这种情况中的 i位必须要写 s那么怎样计算第二种情况的字符串的数量呢？这样算：长度为 i-1的所有字符串的数量-其中不包含u的字符串-包含us的也就是26^(i-1)-25^(i-1)-dp[i-1]那么dp[i]=26^(i-1)-25^(i-1)+25dp[i-1] #include<bits/stdc++.h> #define ll long long using...

dp+离散化设dp[j]的含义是到位置j的陷进数，如果道路长度为1e9的话，数组是开不到这么大的，所以我们必须想办法缩短道路的长度，这就用到离散化了。青蛙每次可以跳s-t之间的数，如果s==t的话，只需要枚举存储陷阱位置的数组，判断当前位置s是否可以走到即可。如果s!=t的话，我们来举个例子讨论下比如s=5 , t=6跳一次 走到 5 - 6跳两次 走到 10 - 12跳三次 走到 15 - 18跳四次 走到 20 - 24跳五次 走到 25 - 30跳六次 走到 30 - 36跳七次 走到 35 - 42跳八次 走到 40 - 48跳九次 走到 45 - 54跳十次 走到 50 - 60我们...

dp[i][j]的状态为前i天，买了j个糖果的最小花费题目说每天最少要有一个糖果吃，那么第i天最少要有i个糖果，最多要有min(n,im),n为天数，im为当天生产的糖果总数，那么dp[i][j]=min(dp[i][j],dp[i-1][k]+C) k>=i-1,j>=i含义就是如果当天不选那么当天最少要有i个糖，选的话，要选几个呢？这要看i-1天选了几个。 只有我们每次都花费最小的糖果，总花费才小，所以我们可以先把每一天的花费从小到大排个序，用前缀和预处理一下。 #include<bits/stdc++.h> using namespace std; const i...

从左往右求最长上升子序列，在从右往左求最长上升子序列。 #include <iostream> #include <vector> #include <algorithm> using namespace std; const int maxn = 105; int arr[maxn]; vector<int>nums(maxn); int dp[maxn]; int dp2[maxn]; int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >&...

dp[i][j]表示左边去了i个数，右边取j个数时所获得最大值 #include <iostream> using namespace std; const int maxn = 1005; int dp[maxn][maxn]; int main() { int t; cin >> t; while (t--) { int num; cin >> num; int nums1[maxn]; int nums2[maxn]; for (int i = 1; i <= num; i++) { cin >> nums1[i]; } for (i...

错误思路：一开始想着用贪心，小渊每次都传给好感度最大的同学，并标记这个同学，小轩传递的时候就传递给没传递过的同学中的最大值，如果这样走的话可能会导致有些只比小渊传给的同学的好感度低一点点的同学，在小轩传递的时候并不能传递到。可以看一下这个样例3 30 72 3880 69 6568 96 0小渊走的路径为0->80->69->96->0小轩走的路径为0->65->38->72>0可以看到68这个点谁都没有传递，但是如果小渊传递给68，而不是69，那么小轩就可以传递给69，不用传递给38，所以不能一味让小渊传递给最大值，我们还要考虑小轩的情况，如果...

记录一个坑点，不能用注释里的代码求最大值，因为如果n多花放完价值和为负数，但n-1朵放完价值和为正数，那么ans保留的就是n-1朵的答案 #include <iostream> #include <algorithm> #include <vector> using namespace std; const int maxn = 105; int arr[maxn][maxn]; long long dp[maxn][maxn]; vector<int>res; int main() { int n, m; cin >> n >...

当前这个点可以由它的左上方的点和正上方的点走到dp[i][j]的含义是走到[i,j]这个点的最大值所以状态转移方程就是 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + nums[i][j]; #include <iostream> using namespace std; const int maxn = 105; int nums[maxn][maxn]; int dp[maxn][maxn]; int main() { int n; cin >> n; for (int i = 1; i <= n; i++) ...

dp[i][j]的含义为s1串的前i长度与s2串的前j长度的最长公共子序列res[i][j]的含义为s1串的前i长度与s2串的前j长度的最长公共子序列长度为dp[i][j]的数目如果s1[i][j]==s2[i][j]那么dp[i][j]=dp[i-1][j-1]+1 res[i][j]=res[i-1][j-1]如果不相等 dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]); 注意 dp[i][j - 1]和 dp[i - 1][j]都包含了dp[i-1][j-1]的情况，所以如果dp[i][j]==dp[i-1][j-1]，res[i][j]应该减去res...

题目要求某个点的滑坡距离最大，要想滑坡距离最大那么这个点的高度就要最高，因为高度最高，他就可以滑向任意一个它四周点，当然也要滑向在它的四周中高度最高的那个点。我们可以定义dp[i][j]的状态为从i，j滑下去的最高长度，那么状态转移方程为dp[i][j]=max(dp[i][j],dp[i-1][j]+1)dp[i][j]=max(dp[i][j],dp[i+1][j]+1),max(dp[i][j],dp[i][j-1]+1),max(dp[i][j],dp[i][j+1]+1)，即dp[i][j]的最大值就是它滑向在它的四周中的最大值的那个点 #include <iostream&g...

题目要求在m次传球之后传到1号位的方案我们可以定义状态在第i次传球之后在j号位的方案，即dp[i][j]的含义状态转移方程就是dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1] 即第i次传球之后再j位置上的方案数等于第i-1次传球在j-1和j+1位置上的方案数，注意j=1和j=n的情况要特判 #include <iostream> using namespace std; const int maxn = 35; int dp[maxn][maxn]; int main() { int n, m; cin >> n >> m; dp[0][...

再加入一个结点之前判断这个节点是否之前存入过，判断这个节点与目标值的大小 class Solution { public: /** * 返回最后要输出的答案 * @param n int整型 表示牛牛的数字 * @param m int整型 表示牛妹的数字 * @return int整型 */ int solve(int n, int m) { // write code here、 int dist[2100]; memset(dist, -1, sizeof(dist)); queue<int> q; dist[n] = 0; q.push(n); while(!q.empty...

用深搜求出子集，枚举每个自己中是否存在limit数组中的元素 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int 集合大小 * @param m int 限制数量 * @param limit Pointvector 不能同时出现的(u,v)集合 * @return int */ int cnt = 0; int vis[25] = { 0 }; void dfs(int k, int n, vector<Point>& limit) { if (k =...