学网站建设与维护/单页面网站如何优化

【题目描述】

【思路】
状态表示：f[i][j]表示中序遍历是w[i]到w[j]的所有二叉树的得分的最大值。
状态计算：f[i][j] = max(f[i][k - 1] * f[k + 1][j] + w[k])，即将f[i][j]表示的二叉树 集合按根节点分类，当根节点在k取最大得分时为 f[i][k - 1] * f[k + 1][j] + w[k]。f[[i]
[j]就是遍历所有k取得的最大。

时间复杂度分析：状态数为N * N,每个状态计算量为O(N)，所以时间复杂度为O(N^3)

import  java.io.*;
import java.lang.Math;
public class Main{static int N = 35;static int w[] = new int [N]; //记录节点分数static int f[][] =  new int[N][N];//f[i][j]记录区间[i,j]的最大分数值static int root[][] = new int[N][N];//记录f[i][j]所对应的根public static void dfs(int l, int r){if(l > r ) return ;int t = root[l][r];//根System.out.print(t+" ");dfs(l, t -1);dfs(t + 1, r);}public static void main(String aregs[])throws Exception{BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(bf.readLine());String s[] = bf.readLine().split(" ");for(int i = 1; i <= n; i++) w[i] = Integer.parseInt(s[i - 1]);//区间dpfor(int len = 1; len <= n; len ++)for(int l = 1; l + len - 1 <= n; l++){int r = l + len -1;//枚举[l,r]区间的根节点for(int k = l; k <= r; k++){//计算左子树和右子树int left = (k == l? 1 : f[l][k - 1]);int right = (k == r? 1 : f[k + 1][r]);int score = left * right + w[k];//叶子结点if( l == r) score = w[k];if( f[l][r] < score){//更新分数和根节点f[l][r] = score;root [l][r] = k;}}}System.out.println(f[1][n]);dfs(1, n);}
}