题解 | #石子合并#

练dp练烦了，突发奇想写了一个记忆化搜索，大致思路是把原来的线性末尾再补一节一样的，对这两段求合并代价。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define endl '\n'
using namespace std;
using ll=long long;
using PII=pair<int,int>;
const int N=410;
int t;
int dmax[N][N],dmin[N][N];

vector<ll>pre(N+1);
vector<int>a(N+1);
ll deal1(int l,int r){
	if(l==r)return 0;
	else if(dmax[l][r]!=0)return dmax[l][r];
	else{
		ll cnt=0;
        rep(i,l+1,r){
           cnt=max(deal1(l,i-1)+deal1(i,r)+pre[r]-pre[l-1],cnt);
		}
		dmax[l][r]=cnt;
        return cnt;
	}
}
ll deal2(int l,int r){
	if(l==r)return 0;
	else if(dmin[l][r]!=0)return dmin[l][r];
	else{
		ll cnt=0x4f4f4f4f;
        rep(i,l+1,r){
           cnt=min(deal2(l,i-1)+deal2(i,r)+pre[r]-pre[l-1],cnt);
		}
		dmin[l][r]=cnt;
        return cnt;
	}

}
void solve(){
	
    int n;cin>>n;
	rep(i,1,n)cin>>a[i];
	rep(i,n+1,n*2)a[i]=a[i-n];
	rep(i,1,n*2)pre[i]=pre[i-1]+a[i];
	ll ans1=0,ans2=0x4f4f4f4f;
	rep(i,1,n){
		ans2=min(ans2,deal2(i,i+n-1));
		ans1=max(ans1,deal1(i,i+n-1));
	}
    cout<<ans2<<endl<<ans1;


}
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	int t=1;
	while(t--){
		solve();
	}
	return 0;
}