树与并查集
就是想求连通子集的个数
#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<=nint 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++){//长度还是最大nfor(int j = 1;j+len<=2*n;j++){//起点枚举最大到2*n-1,ends<=2*n-1int 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]);
}