归属树形DP 做着更像记忆化
DP很好做 就是那个输出路径恶心了。。改代码 从60多行改到120多行。。dp从1维加到三维。。
先类似记忆化搜索整棵树 枚举以i为根节点的最大值 子树类似
求完最大值 再递归搜一下前序 这题不记忆化会超时
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 using namespace std; 7 #define LL long long 8 LL dp[35][35][35],a[35]; 9 int n,path[35],to; 10 LL dfs(int root,int l,int r) 11 { 12 if(dp[root][l][r]) 13 return dp[root][l][r]; 14 if(l==r) 15 return dp[root][l][r] = a[l]; 16 int i,j; 17 LL tt =0; 18 if(l==root) 19 { 20 for(i = root+1 ; i <= r ; i++) 21 tt = max(tt,dfs(i,root+1,r)+a[root]); 22 } 23 else if(r==root) 24 { 25 for(i = l ; i < root ; i++) 26 tt = max(tt,dfs(i,l,root-1)+a[root]); 27 } 28 else 29 { 30 for(i = l; i < root ; i++) 31 for(j = root+1 ; j <= r; j++) 32 { 33 LL s1 = dfs(i,l,root-1); 34 LL s2 = dfs(j,root+1,r); 35 tt = max(tt,s1*s2+a[root]); 36 } 37 } 38 return dp[root][l][r]=tt; 39 } 40 void find(int u,int l,int r,int v) 41 { 42 int i,j,x1,x2; 43 if(l==r) 44 return ; 45 int f = 0; 46 if(u==l) 47 { 48 for(i = u+1 ; i <= r ; i++) 49 if(dp[i][u+1][r]+a[u]==dp[u][l][r]) 50 { 51 x1 = i; 52 break; 53 } 54 path[v+1] = x1; 55 find(x1,u+1,r,v+1); 56 } 57 else if(u==r) 58 { 59 for(i = l ; i < u ; i++) 60 if(dp[i][l][u-1]+a[u]==dp[u][l][r]) 61 { 62 x1 = i; 63 break; 64 } 65 path[v+1] = x1; 66 find(x1,l,u-1,v+1); 67 } 68 else 69 { 70 for(i = l; i < u ; i++) 71 { 72 for(j = u+1; j <= r ;j++) 73 if(dp[i][l][u-1]*dp[j][u+1][r]+a[u]==dp[u][l][r]) 74 { 75 x1 = i; 76 x2 = j; 77 f = 1; 78 break; 79 } 80 if(f) break; 81 } 82 path[v+1] = x1; 83 path[v+1+u-l] = x2; 84 find(x1,l,u-1,v+1); 85 find(x2,u+1,r,v+1+u-l); 86 } 87 } 88 int main() 89 { 90 int i; 91 cin>>n; 92 for(i = 1; i <= n ; i++) 93 cin>>a[i]; 94 LL ans = 0; 95 for(i = 1; i <= n ; i++) 96 { 97 LL s = dfs(i,1,n); 98 if(s>ans) 99 { 100 ans =s; 101 path[1] = i; 102 } 103 } 104 cout<<ans<<endl; 105 find(path[1],1,n,1); 106 for(i = 1; i < n ; i++) 107 cout<<path[i]<<" "; 108 cout<<path[n]<<endl; 109 return 0; 110 }