Living-Dream 系列笔记第79期

0-0 / 2024-09-21 / 原文

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