我认为这题很好的揭示了并查集的一个本质，即将任何有关联的元素整合到一个集合里。 首先是一个常规解法，思路是通过边的权值来维护两者间的关系。  这题对于并查集的的考察并没有很常规，我们还可以用另一个思路，把情况拆分一下 ，更加简洁  #include<bits/stdc++.h> using namespace std; int fa[201000],n,k; int find(int a){ if(fa[a]==a) return a; else return fa[a]=find(fa[a]); } void merge(int a, int b){ fa[find(a)]=fi...

相同点:1.两者都需要满足一个条件，即我这一步的最优决策是可以基于上一步决策确定后的结果来求出的。 意思说我在上一步决策确定后，我做这一步决策是不会影响上一步决策的。 2.都利用了递归的思想，即在一个结果的基础上去求解下一个结果，最后求出目标解 不同点：I.动态规划：动态规划的关键在于推出一个递推方程，他的求解结果是自上而下的； eg：  for(int i=2; i<=f; i++){ for(int j=1; j<=v; j++){ for(int k=1; k<j; k++) dp[i][j]=max(dp[i][j],dp[i-1][k]+mp[i][j]);//需要...

这题符合动态规划的条件，即在每选一盆花时，选这盆花的操作不受上次选择的干扰，每一次维护数组时，都维护出了选第i盆花时的最优解 #include<bits/stdc++.h> using namespace std; typedef long long ll; int f,v; int mp[200][200]; int dp[200][200]; int main(){ cin>>f>>v; for(int x=1; x<=f; x++){ for(int y=1; y<=v; y++){ cin>>mp[x][y]; } } mem...

我们可以发现，每一步的最优解就是选择这座山右边第一高的或者左边第一高的，所以很明显，要用单调栈来进行一个维护。 //还差一个条件的实现，就是从右开始向后扫，找最右边第一个比堆顶大时 //碰见重复的连续串，应该选择第一个；找左边的则是找最后一个 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int M=1e6+7; int g[M],h[M],l[M],r[M]; int f[M]; int t,n; stack<int> q; int jud(int a, int b){...

这题用到了分治思想，后序遍历的存图方式是：左->右->根，所以反过来存图的话顺序应该是：根->右->左，然后进行一个存图即可 ```#include<bits/stdc++.h> using namespace std; int a; int numb[50]; int ans[50]; int la; void mp(int x){ ans[x]=numb[la--]; if(2*x+1<=a) mp(2*x+1); if(2*x<=a) mp(2*x); } int main(){ cin>>a; la=a; for(int i=...

知识点：链式前向星存图+记忆化搜索（dfs） 每个节点到终点的路径为他的所有子节点到终点路径的数量和，边界即为该节点就是终点，此时这个节点到终点的路径条数为1； ">using namespace std; const int N=550; int n,m; int x,y; int e[N*N],ne[N*N],h[N],idx; int deg[N]; int num[N]; void add(int a,int b){ e[idx]=b,ne[idx]=h[a],h[a]=idx++; } bool f=false; //x为起点 y为终点 int dfs(int u){ if(num[...

本质上就是一个链式前向星建图加一个简单地查找（注意这里是双向图），没什么太大的难点，但是样例中的第四条路线过不了（但是我感觉是可行的），所以代码无法处理第四条路线这样的数据。 ">using namespace std; int n,m;//点个数和路径条数 int x,y,z;//点1,点2，费用 int cnt,k,cost;//k行攻略 int mp[600]; long long ans; struct point{ int t,next,co; }edge[2000]; int head[500]; void addedge(int x,int y,int z){ edge[++cn...

学到动态规划学到后面反而忘了他最重要的本质， 动态规划的本质是一个状态和一个状态之间的转换。 本来开了个三维数组dp[i][j][k],代表的是从左拿了个，从右拿了j个，现在是第几个，其实简化后就成了dp[i][j]。 代码中的实现在两层循环可以实现，第一层枚举现在一共选了n个数，然后第二层枚举从左取了x个数，然后每一层的的状态就是dp[i][n-i](三个循环是整不过的） ```#include<bits/stdc++.h> using namespace std; typedef long long ll; int a[1100],b[1100]; ll ans[1100][1...

从左边求一次最大上升子串，再从右边选一次，每一个人只有两个状态：选或者不选，每次维护后求解一段区间的最大值，符合动态规划思想，以下为代码 ">using namespace std; int n; int stu[500],l[500],r[500]; int main(){ cin>>n; for(int i=1; i<=n; i++) cin>>stu[i]; for(int i=1; i<=n; i++){ l[i]=1; for(int x=1; x<=i; x++){ if(stu[i]>stu[x]) l[i]=max(l[i],l[...

#include<bits/stdc++.h> using namespace std; int main() { int o[100],u[100],s[100]; memset(o,0,sizeof(o)); memset(s,0,sizeof(s)); memset(u,0,sizeof(u)); int n; int cto=0; int ctu=0; long long sum=0; char wr[100]; scanf("%d",&n); scanf("%s",...

#include<bits/stdc++.h> #define ll long long using namespace std; void re(ll a, ll b){ if(a>b) printf("a is the winner!"); if(a<b) printf("b is the winner!"); if(a==b) printf("There is no winner!");...