RMQ算法讲完没几个小时，我们就开始了小紫中的一节（足见这个算法很重要）——树形动归；
参考资料：
1.焦作一中信息学oy（http://www.cnblogs.com/gq-ouyang/archive/2013/02/26/2933431.html
2.小黄（信息学奥赛一本通）
3.小紫（算法竞赛入门经典第二版）
题型总结：（来自资料1
1、加分二叉树：区间动规+树的遍历；
2、二叉苹果树：二叉树上的动规；
3、最大利润：多叉树上的动规；
4、选课：多叉树转二叉；
5、选课（输出方案）：多叉转二叉+记录路径；
6、软件安装：判断环+缩点+多叉转二叉；
学习目标：
1.熟练掌握树形动规（小紫刷掉，资料一刷掉）；
2.复习树的相关知识；
（二叉树的分支确定且可以为空，具有良好的递归特性，程序设计很方便，故常将多叉树转二叉树（小黄））
一.加分二叉树
题意：树的结构动规（！=树形动规，是根据树的结构的动规）（n<30节点），（分数<100）
题目分析：分左右，要熟练遍历顺序；老师没让写......代码是资料一里的
#include<iostream> #include<iomanip> #include<cstring> #include<cstdio> #include<cmath> #include<memory> #include<algorithm> #include<string> #include<climits> #include<queue> #include<vector> #include<cstdlib> #include<map> using namespace std; const int ee=50,e=-999999999; int n; int a[ee]={0},f[ee][ee],root[ee][ee]={0};//f(i,j)中序遍历为i,i+1,…,j的二叉树的最大加分 //**若根节点的下表是k，则左端点的是k-1，右端点是k+1； void front(int x,int y) { if(root[x][y]!=0) cout<<root[x][y]<<' '; if(root[x][root[x][y]-1]!=0) front(x,root[x][y]-1); if(root[root[x][y]+1][y]!=0) front(root[x][y]+1,y); } int main() { //freopen("in.in","r",stdin); //memset 赋初值不能为1 memset(f,1,sizeof(f)); cin>>n; for(int i=0;i<=n;i++) { for(int j=0;j<=n;j++) f[i][j]=1; } for(int i=1;i<=n;i++) { cin>>a[i]; f[i][i]=a[i]; root[i][i]=i; } //区间长度 for(int len=1;len<=n;len++) { //区间起点 for(int i=1;i<=n;i++) { //终点 int j=i+len; if(j<=n) { int temp=e; //因为是中序排列 for(int k=i;k<=j;k++) { if(temp < (f[i][k-1]*f[k+1][j]+a[k])) { temp=f[i][k-1]*f[k+1][j]+a[k]; root[i][j]=k; } } f[i][j]=temp; } } } cout<<f[1][n]; //前序遍历 cout<<endl; front(1,n); fclose(stdin);fclose(stdout); return 0; }
二.URAL_1018 二叉苹果树
题意：每个边(共n）带权值，给定保留边数目（q)，算最大权值；1<=Q<= N,1<N<=100
题目分析：这里用了一个后来都会用到的思想，就是因为边没有点好记，所以可以把边上的分数记在点上，并且给根节点加一条边，这样边数加一以后就不需要分开讨论了；其中createtree递归由上而下不太好理解，我写错了很多次；
#include<cstdio> #include<iostream> #include<cmath> #include<cstdlib> #include<cstring> #include<string> #include<algorithm> #include<queue> #include<set> using namespace std; int n,f[105][105],vis[105],sta[105],fin[105],amo[105],q; struct node { int apples,lefloc,rigloc; }thran[105]; void createtree(int k) { vis[k]=1; for(int i=1;i<=n-1;i++) if(sta[i]==k||fin[i]==k) { int t=sta[i]+fin[i]-k;//被确认的点是子节点 if(vis[t])continue;//自上而下判重； createtree(t);//把建树向下传递递归 if(!thran[k].lefloc) { thran[k].lefloc=t;//传递节点 thran[t].apples=amo[i]; } else {//用lefloc就是提醒自己，这个和线段树不一样，直接记节点 thran[k].rigloc=t; thran[t].apples=amo[i]; break;} } } void dp(int k) { if(thran[k].lefloc) { int lef=thran[k].lefloc; int rig=thran[k].rigloc; dp(lef); dp(rig); for(int i=1;i<=q+1;i++)//还可以再简化，因为在除根节点以外不可能取满 for(int j=0;j<=i-1;j++)//一边可为0 f[k][i]=max(f[k][i],f[lef][j]+f[rig][i-j-1]+thran[k].apples); //必选根 } else { f[k][1]=thran[k].apples; f[k][0]=0; } } int main() { freopen("apple.in","r",stdin); freopen("apple.out","w",stdout); scanf("%d %d",&n,&q); for(int i=1;i<=n-1;i++)//n-1条边 scanf("%d %d %d",&sta[i],&fin[i],&amo[i]); createtree(1);//从1建树确保了后来的上下确定 dp(1) ;//递归动规 cout<<f[1][q+1]; return 0; }