【题解】LOJ #2292. 「THUSC 2016」成绩单【20201124 NOIP 模拟赛】【区间DP】

题目链接

题目链接

题目链接

题意

今有一个序列 (w)，给定 (a,b)，你一次操作可以选择区间 ([l,r])，花费 (a+b(max_{i=l}^r w_i-min_{i=l}^r w_i)^2)，并将这段区间删掉。问将序列删空的最小花费。(nleq 50)

题解

设 (f[l,r]) 为删除 ([l,r]) 的最小花费，(g[l,r,p,q]) 为删除 ([l,r]) 的一部分部分直到剩下的最小值为 (p),最大值为 (q) 的最小花费。

• 用 (g[l,r,p,q]+a+b(q-p)^2) 更新 (f[l,r])；
• 用 (g[l,r,p,q]) 更新 (g[l,r+1,p',q'])（不把 (w_{r+1}) 拆出去）；
• 用 (g[t,l-1,p,q]+f[l,r]) 更新 (g[t,r])（把 ([l,r]) 拆出去）。

(O(n^5)) DP。

#include<bits/stdc++.h>
using namespace std;
const int N=52;
int f[N][N],g[N][N][N][N],w[N],v[N],m,n,a,b;
int main(){
	scanf("%d%d%d",&n,&a,&b);
	for(int i=0;i<n;i++)scanf("%d",w+i),v[i]=w[i];
	sort(v,v+n);	m=unique(v,v+n)-v;
	for(int i=0;i<n;i++)w[i]=lower_bound(v,v+m,w[i])-v;
	memset(f,0x3f,sizeof(f));
	memset(g,0x3f,sizeof(g));
	for(int r=0;r<n;r++){
		for(int l=r;~l;l--){
			int mx=-23333,mn=23333;
			for(int i=l;i<=r;i++)mx=max(mx,w[i]),mn=min(mn,w[i]);
			g[l][r][mx][mn]=0;
			for(int p=0;p<m;p++)
				for(int q=p;q<m;q++){
					f[l][r]=min(f[l][r],g[l][r][p][q]+a+b*(v[q]-v[p])*(v[q]-v[p]));
					if(r+1<n){
						int &g_=g[l][r+1][min(p,w[r+1])][max(q,w[r+1])];
						g_=min(g_,g[l][r][p][q]);
					}
				}
			for(int p=0;p<m;p++)
				for(int q=p;q<m;q++)
					for(int t=0;t<l;t++)
						g[t][r][p][q]=min(g[t][r][p][q],g[t][l-1][p][q]+f[l][r]);
		}
	}
	cout<<f[0][n-1]<<endl;
}