【DP】区间DP入门 (2)

代码：

#include<bits/stdc++.h> using namespace std; const int N=105; int n; int w[N<<1]; int f[N<<1][N<<1]; int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>w[i]; w[n+i]=w[i]; } for(int len=3;len<=n+1;len++) for(int l=1;l+len-1<=2*n;l++){ int r=l+len-1; for(int k=l+1;k<=r-1;k++) f[l][r]=max(f[l][r],f[l][k]+f[k][r]+w[l]*w[k]*w[r]); } int res=0; for(int i=1;i<=n;i++) res=max(res,f[i][i+n]); cout<<res<<endl; return 0; }

记忆化搜索版本：

#include<bits/stdc++.h> using namespace std; const int N=210; int n; int w[N]; int f[N][N]; int dp(int l,int r){ if(f[l][r]>=0) return f[l][r]; if(r==l || r==l+1) return f[l][r]=0; int &v=f[l][r]; for(int k=l+1;k<=r-1;k++){ v=max(v,dp(l,k)+dp(k,r)+w[l]*w[k]*w[r]); } return v; } int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>w[i]; w[n+i]=w[i]; } memset(f,-1,sizeof f); int res=0; for(int i=1;i<=n;i++) res=max(res,dp(i,i+n)); cout<<res<<endl; return 0; } 加分二叉树：https://www.acwing.com/problem/content/481/

分析

g[l][r] 表示 \([l,r]\) 的根节点。
将中序遍历的序列看作是区间求解，然后枚举根节点（将它作为断点），记录答案的过程中要注意当答案得到更新的时候才记录这个区间的根节点。

#include<bits/stdc++.h> using namespace std; const int N=35; int f[N][N]; //dp int g[N][N]; //path int n; int w[N]; void dfs(int l,int r){ if(l>r) return; int root=g[l][r]; cout<<root<<' '; dfs(l,root-1); dfs(root+1,r); } int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>w[i]; for(int len=1;len<=n;len++) for(int l=1;l+len-1<=n;l++){ int r=l+len-1; if(len==1){ f[l][r]=w[l]; g[l][r]=l; } else{ 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(score>f[l][r]){ f[l][r]=score; g[l][r]=k; } } } } cout<<f[1][n]<<endl; dfs(1,n); return 0; }