树
形DP，需要记录方案，并注意空树的情况.[状态]f[i][j]从结点i到j的最大加分值[方程]f[i][j] = max{f[i][k-1]*f[k+1][j]+a[k]} (i<=k<=j)实现方程的时候循环顺序非常关键:结点数由小到大循环.否则会出现需要的值未计算的情况.记录方案可以用一个数组d[i][j]记录k，然后递归寻找方案并记录.
1 #include<stdio.h>
2 #include<iostream>
3 using namespace std;
4 int f[35][35] = {0}, d[35][35] = {0}, ans[35] = {0}, t = 0;
5 void print(int start, int end){
6 if (start > end) return;
7 if (start == end) {ans[++t] = start; return;}
8 ans[++t] = d[start][end];
9 print(start, d[start][end]-1);
10 print(d[start][end]+1, end);
11 }
12 int main(){
13 int n, a[35] = {0}, i, j, k, l;
14 scanf("%d", &n);
15 for (i = 1; i <= n; i++){
16 scanf("%d", &a[i]);
17 f[i][i-1] = 1;
18 f[i][i] = a[i];
19 }
20 for (l = 2; l <= n; l++)
21 for (i = 1; i <= n; i++)
22 for (k = i; k <= i+l-1; k++){
23 j = i+l-1;
24 if (f[i][j] < f[i][k-1]*f[k+1][j] + a[k]){
25 f[i][j] = f[i][k-1]*f[k+1][j] + a[k];
26 d[i][j] = k;
27 }
28 }
29 printf("%d\n", f[1][n]);
30 print(1, n);
31 for (i = 1; i < t; i++) printf("%d ", ans[i]);
32 printf("%d\n", ans[t]);
33 }
34