P1775
典。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e2+5;
int n,a[N],sum[N],dp[N][N];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n;
memset(dp,0x3f,sizeof dp);
for(int i=1;i<=n;i++)
cin>>a[i],sum[i]=sum[i-1]+a[i],dp[i][i]=0;
for(int l=2;l<=n;l++){
for(int i=1;i+l-1<=n;i++){
int j=i+l-1;
for(int k=i;k<j;k++)
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
dp[i][j]+=sum[j]-sum[i-1];
}
}
cout<<dp[1][n];
return 0;
}
P1040
很容易发现这玩意是个区间 dp。因为中序遍历是 左-根-右 的，考虑枚举根。
状态：令 \(dp_{i,j}\) 表示区间 \([i,j]\) 的最高加分。
初始：\(dp_{i,i}=a_i,dp_{i,i-1}=1\)。
转移：\(dp_{i,j}=dp_{i,k} \times dp_{k+1,j} + a_k\)。
答案：\(dp_{1,n}\)。
每次转移成功时顺便记录根即可。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=35;
int n,a[N],dp[N][N],rt[N][N];
void dfs(int l,int r){
if(l>r)
return;
cout<<rt[l][r]<<' ';
dfs(l,rt[l][r]-1);
dfs(rt[l][r]+1,r);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i],dp[i][i]=a[i],dp[i][i-1]=1,rt[i][i]=i;
for(int l=2;l<=n;l++){
for(int i=1;i+l-1<=n;i++){
int j=i+l-1;
for(int k=i;k<j;k++)
if(dp[i][j]<dp[i][k-1]*dp[k+1][j]+a[k])
dp[i][j]=dp[i][k-1]*dp[k+1][j]+a[k],rt[i][j]=k;
}
}
cout<<dp[1][n]<<'\n';
dfs(1,n);
return 0;
}