可以用一个二元组（或者说区间左右端点）[L,R]表示当前递归层次的状态，dfs(L,R)=求区间[L,R]对应二叉树子树能获得的最大分数，为了能在线段区间中模拟树结构的递归深搜过程，可以进行下图的操作

动规的思路也很清晰，套用区间型动规的通用方程就行，f[L,R]=max{f[L,mid-1]*f[mid+1,R]+value[mid]},这里mid就是要取的子树根结点

#include 
       
        
#include 
        
          #include 
         
           #define MAXN 100 int f[MAXN][MAXN]; //f[i][j]=中序遍历序列区间[1,j]获得分数的最大值 int visit[MAXN][MAXN]; int root[MAXN][MAXN]; int max(int a,int b) { if(a>b) return a; return b; } int dp(int L,int R) // { if(L==R) return f[L][R]; if(L>R) return 1; if(visit[L][R]) return f[L][R]; visit[L][R]=1; int maxAns=-1; for(int mid=L;mid<=R;mid++) if(maxAns<(dp(L,mid-1)*dp(mid+1,R)+f[mid][mid])) { root[L][R]=mid; int Ltree=dp(L,mid-1); int Rtree=dp(mid+1,R); maxAns=(Ltree*Rtree+f[mid][mid]); } return f[L][R]=maxAns; } void firstPrint(int L,int R) { if(L>R) return; printf("%d ",root[L][R]); firstPrint(L,root[L][R]-1); firstPrint(root[L][R]+1,R); } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&f[i][i]); root[i][i]=i; } printf("%d\n",dp(1,n)); firstPrint(1,n); printf("\n"); system("pause"); return 0; }
         
        
       

序列型动态规划

1、Wikioi 1058 合唱队形

题目描述 Description

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。

合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足T1<... Ti+1>…>TK(1<=i<=K)。

你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

输入描述 Input Description

输入文件chorus.in的第一行是一个整数N(2<=N<=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。

输出描述 Output Description

输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

样例输入 Sample Input

8
186 186 150 200 160 130 197 220

样例输出 Sample Output

4

数据范围及提示 Data Size & Hint

对于50％的数据，保证有n<=20；
对于全部的数据，保证有n<=100。

此题可以用最长上升子序列和最长下降子序列做，不过有些细节需要处理，如图

#include 
       
        
#include 
        
          #include 
         
           #define MAXN 300 int high[MAXN]; //high[i]=第i个同学的身高 int up[MAXN],dn[MAXN]; int max(int a,int b) { if(a>b) return a; return b; } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&high[i]); up[i]=dn[i]=1; } for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) if(high[j]
          
           =1;i--) for(int j=n;j>=i;j--) if(high[j]
           
            
 
            
 
            
 
            
 
            
 
            
 
            

 
 
            

 
 
            

 
 ?? ??