树与并查集，区间dp，树形dp

树与并查集

就是想求连通子集的个数

#include<iostream> using namespace std; const int MAX = 1000010; //数组的最大长度（即图中点个数的最大值） int m, n; //当前图的长宽规格 int pre[MAX]; //用于存放每个点的根节点 void fun1(int n) //初始化函数 { for (int i = 1;i <= n;i++) pre[i] = i; } int fun2(int key) //寻找根节点函数 { if (pre[key] == key) return key; return pre[key] = fun2(pre[key]); } void fun3(int x, int y) //联合函数 { int rootx = fun2(x); int rooty = fun2(y); if (rootx != rooty) pre[rootx] = rooty; } int main() { int x, y, line; cin >> m >> n >> line; fun1(m * n); for (int i = 0;i < line;i++) { cin >> x >> y; fun3(x, y); } int ans = 0, a[MAX] = { 0 }; for (int i = 1;i <= m * n;i++) a[fun2(i)] = 1; for (int i = 1;i <= m * n;i++) if (a[i]) ans++; cout << ans << endl; return 0; }

已知前序遍历顺序，即根节点即为该序列的第一个结点，每次获取第一个结点就可以将该子树分为左右子树，最后再分别递归左右子树，因为是要输出后序遍历顺序，所以先递归左子树，再递归右子树，最后将标记的根节点输出

# include<iostream> # include<string> # include<cstring> # include<cstdio> using namespace std; string a, b; void work(string b,string a) { if (b.empty()) return ; char root = b[0]; int k = a.find(root); b.erase(b.begin()); string bleft = b.substr(0, k); string aleft = a.substr(0, k); string bright = b.substr(k); string aright = a.substr(k + 1); work(bleft, aleft); work(bright, aright); cout << root; } int maim() { cin >> a >> b; work(b, a); cout << endl; return 0; }

 

就是二叉树的前序遍历

# include<iostream> # include<string> using namespace std; int n; char t, tt; struct tree { char l; char r; }; tree node[300]; void work(char x) { if (x == '*')return; cout << x; work(node[x].l); work(node[x].r); } int main() { cin >> n; cin >> t; char a, b; cin >> a >> b; node[t].l = a, node[t].r = b; for (int i = 2; i <= n; i++) { cin >> tt; cin >> node[tt].l >> node[tt].r; } work(t); return 0; }

跟此类第一题一样 

#include<cstdio> #include<iostream> #include<cstring> using namespace std; void beford(string in,string after){ if (in.size()>0){ char ch=after[after.size()-1]; cout<<ch;//找根输出 int k=in.find(ch); beford(in.substr(0,k),after.substr(0,k)); beford(in.substr(k+1),after.substr(k,in.size()-k-1)); } } int main(){ string inord,aftord; cin>>inord;cin>>aftord;//读入 beford(inord,aftord);cout<<endl; return 0; }  区间dp

区间DP的核心在于将一个大区间分解成小区间，并通过处理小区间来求解大区间的问题。这种方法通常涉及两个步骤：记忆化搜索和递推。在递推过程中，关键是确定循环的顺序和状态转移方程。大多数区间DP问题都可以通过确定大区间如何转化为小区间，找出边界条件，然后进行动态规划求解。

memset(dp,0,sizeof(dp))//初始dp数组 for(int len=2;len<=n;len++){//枚举区间长度 for(int i=1;i<n;++i){//枚举区间的起点 int j=i+len-1;//根据起点和长度得出终点 if(j>n) break;//符合条件的终点 for(int k=i;k<=j;++k)//枚举最优分割点 dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+w[i][j]);//状态转移方程 } }

 令dp[i][j]表示石子中第i堆到第j堆合并的最小代价，则 j~ends 堆合并 = 较小的（原来， 分割点i坐部分重量 + 分割点i右边部分重量 + 合并后两堆总重量），该问题的转移方程可以总结如下：

dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+weigth[i][ends]);

#include <iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; #define INF 0x3f3f3f int stone[105]; int dp[105][105]; int sum[105]; int main() { int n; scanf("%d",&n); memset(sum,0,sizeof(sum)); memset(dp,INF,sizeof(dp)); for(int i =1;i<=n;i++){ scanf("%d",&stone[i]); sum[i] = sum[i - 1] + stone[i];//重量 dp[i][i] = 0; } for(int len = 1;len<=n;len++){//枚举长度 for(int j = 1;j+len<=n+1;j++){//枚举起点，ends<=n int ends = j+len - 1; for(int i = j;i<ends;i++){//枚举分割点 dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+sum[ends]-sum[j-1]);//更新状态 } } } cout<<dp[1][n]<<endl; return 0; }

环状以后合并区间的情况就可以从后往前合并，最后合并完成可能是1~n,2~n~1,3~n~2.....这种n个石子合并的情况。所以我们可以破环成链，将前n-1各元素也放到n后面构成一个线性的环状序列，在对这个序列进行线性dp即可

#include <iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; #define INF 0x3f3f3f int stone[105]; int dpmin[205][205];//最小 int dpmax[205][205];//最大 int sum[205]; int main() { int n; scanf("%d",&n); memset(sum,0,sizeof(sum)); memset(dpmin,INF,sizeof(dpmin)); memset(dpmax,-1,sizeof(dpmax)); for(int i =1;i<=n;i++){ scanf("%d",&stone[i]); sum[i] = sum[i - 1] + stone[i]; dpmin[i][i] = 0; dpmax[i][i] = 0; } for(int i = 1;i<=n;i++){ sum[i+n] = sum[i+n-1]+stone[i];//展开的n后面的n-1~1重量 dpmin[i+n][i+n] = 0; dpmax[i+n][i+n] = 0; } for(int len = 1;len<=n;len++){//长度还是最大n for(int j = 1;j+len<=2*n;j++){//起点枚举最大到2*n-1,ends<=2*n-1 int ends = j+len - 1; for(int i = j;i<ends;i++){//注意！i<ends！！！因为i=ends时，dp[ends+1][ends]是不成立的！ dpmin[j][ends] = min(dpmin[j][ends],dpmin[j][i]+dpmin[i+1][ends]+sum[ends]-sum[j-1]); dpmax[j][ends] = max(dpmax[j][ends],dpmax[j][i]+dpmax[i+1][ends]+sum[ends]-sum[j-1]); } } } int ansmin = 0xfffffff; int ansmax = -1; for(int i = 1;i<=n;i++){ ansmin = min(ansmin,dpmin[i][i+n-1]);//找1~n,2~n~1,3~n~2....的合并n个堆的中最大和最小的值 ansmax = max(ansmax,dpmax[i][i+n-1]); } cout<<ansmin<<endl; cout<<ansmax<<endl; return 0; } 树形dp

在树形DP中，我们通常会先处理子树的问题，然后再将子树的解合并到父节点上。这个过程类似于树的后序遍历，即先访问所有子节点，然后再访问父节点。例如，我们可以定义状态f[i]表示以节点i为根的子树的某种性质，然后通过子节点的状态来更新父节点的状态。

# 定义树的节点数量 n = 10 # 初始化树的边和节点权值 edges = [(1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7)] weights = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] # 初始化状态数组 f = [[0 for _ in range(2)] for _ in range(n + 1)] # 定义递归函数来进行树形DP def dfs(u, parent): f[u][0] = 0 f[u][1] = weights[u] for v in tree[u]: if v == parent: continue dfs(v, u) f[u][0] += max(f[v][0], f[v][1]) f[u][1] += f[v][0] # 构建树的邻接表 tree = [[] for _ in range(n + 1)] for u, v in edges: tree[u].append(v) tree[v].append(u) # 从根节点开始递归 dfs(1, -1) # 输出最终结果 print(max(f[1][0], f[1][1]))

就是按模板写

#include<iostream> #include<math.h> #include<string.h> using namespace std; const int N=6000+10; int last[N]; int ne[N],edge[N],cnt=1; bool biao[N]; void add(int a, int b){ edge[cnt] = b; ne[cnt] = last[a]; last[a] = cnt++; } int dp[N][2]; int a[N]; void dps(int root) { dp[root][0]=0;//不选root号节点； dp[root][1]=a[root];//选root号节点 for(int i=last[root];i>=1;i=ne[i]) { int j=edge[i]; dps(j); dp[root][0]+=max(dp[j][0],dp[j][1]); dp[root][1]+=dp[j][0]; } } int main() { int n; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; //因为0包含的有边 int x,y; for(int i=1;i<n;i++)//n-1条边 {cin>>x>>y;//y是x的直接上司 add(y,x); biao[x]=true;//a有父节点b } int v=1; while(biao[v])v++;//找到没有父节点的点 dps(v); cout<<max(dp[v][1],dp[v][0]); }