樹
形DP，需要記錄方案，并注意空樹的情況.[狀態(tài)]f[i][j]從結(jié)點(diǎn)i到j(luò)的最大加分值[方程]f[i][j] = max{f[i][k-1]*f[k+1][j]+a[k]} (i<=k<=j)實(shí)現(xiàn)方程的時(shí)候循環(huán)順序非常關(guān)鍵:結(jié)點(diǎn)數(shù)由小到大循環(huán).否則會(huì)出現(xiàn)需要的值未計(jì)算的情況.記錄方案可以用一個(gè)數(shù)組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