Living-Dream 系列笔记 第79期

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;
}