洛谷 P5336 [THUSC2016]成绩单 题解

洛谷原题

这是蒟蒻写的第一篇黑题的题解

本题解初发于我的blog

这题有多个转移的方程，一下我慢慢叙述

这题很明显可以允许一个\(O(n^5)\)的复杂度，
\(O(n^6)\)很常数一大就很可能超时，

我们用一个四维数组\(f[i][j][l][r]\)表示把 \(i\) 到 \(j\) 之间的值离散化后在取一些数(可以不取)在 \([l,r]\) 之间的最小代价。

很明显，我们可以分两种情况

\(l=r=0\) 和 $l \neq 0 $ 或 $r \neq 0 $

对于\(l=r=0\) 的情况

我们可以都取完，也可以先不取这一个区间。

则 $f[i][j][0][0]=min(a+b * (max_{k=i}^{{j}-min_{k=i}}{j})^{{2},min_{x=1}}{tot} min_{y=x}^{{tot}(w[y]-w[x])}{2}) $

对于$l \neq 0 $ 或 $r \neq 0 $ 的情况

我们可以分为四种情况

如果\(i=j\) 时，很明显区间只有一个数，当\(l\leq w[i]\)(离散化后的值)\(\leq r\)，代价为 \(0\) ，否则为\(INF\)。

如果\(i \neq j\) 时，这有枚举中间转移节点，

有三种情况，分别是：

左区间取而右区间不取

左区间不取而右区间取

左区间不取而右区间不取

则 \(f[i][j][l][r]=min_{k=i}^{j-1}min(f[i][k][0][0]+f[k+1][j][l][r],f[i][k][l][r]+f[k+1][j][0][0],f[i][k][l][r]+f[k+1][j][l][r])\)

代码实现：

#include
#include
#define re register
using namespace std;
template
inline void read(T&x)
{
	x=0;
	char s=getchar();
	bool f=false;
	while(!(s>='0'&&s<='9'))
	{
		if(s=='-')
			f=true;
		s=getchar();
	}
	while(s>='0'&&s<='9')
	{
		x=(x<<1)+(x<<3)+s-'0';
		s=getchar();
	}
	if(f)
		x=(~x)+1;
	return;
}
const int N=56,INF=0x3f3f3f3f;
int n,a,b,f[N][N][N][N],w[N],p[N],tot,c[N];//w[i]是离散化后的值，c[i]是离散化前的值，p[i]是去重后的值 
bool vis[N][N][N][N];
inline int dp(int i,int j,int l,int r)
{
	int &ans=f[i][j][l][r];
	if(vis[i][j][l][r])
		return ans;
	vis[i][j][l][r]=true;
	ans=INF;
	if(!l&&!r)
	{
		re int x=-INF,y=INF;
		for(re int k=i; k<=j; k++)
		{
			x=max(x,c[k]);
			y=min(y,c[k]);
		}
		ans=min(ans,a+b*(x-y)*(x-y));
		for(x=1; x<=tot; x++)
			for(y=x; y<=tot; y++)
				ans=min(ans,dp(i,j,x,y)+a+b*(p[y]-p[x])*(p[y]-p[x]));
		return ans;
	}
	else
	{
		if(i==j)
		{
			if(l<=w[i]&&w[i]<=r)
				ans=0;
			return ans;
		}
		for(re int k=i; k