做题记录整理dp14 P5336 [THUSC2016]成绩单（2022/9/27）

P5336 [THUSC2016]成绩单
这题难度标的虚高
首先一眼区间dp，然后写出递推方程
然后发现爆空间，再上离散化
然后就没了。。。
撑死也就是蓝题
不过学到了一个离散化技巧

#include<bits/stdc++.h>
#define for1(i,a,b) for(ll i = a;i<=b;i++)
#define ll long long
#define mp(a,b) make_pair(a,b)
using namespace std;
ll dp[65][65][65][65],ans[105][105],a[105],b[105],n,aa,bb;
int main(){
	memset(dp,0x3f,sizeof(dp));
	memset(ans,0x3f,sizeof(ans)); 
	
	scanf("%lld",&n);
	scanf("%lld%lld",&aa,&bb);
	
	for1(i,1,n) scanf("%lld",&a[i]),b[i]=a[i];
    sort(b+1,b+1+n);
	int m=unique(b+1,b+1+n)-b-1;
	for1(i,1,n) a[i]=lower_bound(b+1,b+1+m,a[i])-b;//离散化
	for1(i,1,n) dp[i][i][a[i]][a[i]]=0,ans[i][i]=aa;
	
	for1(len,1,n)
	{
		for(ll l=1;l+len-1<=n;l++)
		{
			int r=l+len-1;
			for1(x,1,m)	
				for1(y,x,m)
				{
					dp[l][r][min(x,a[r])][max(y,a[r])]=min(dp[l][r][min(x,a[r])][max(y,a[r])],dp[l][r-1][x][y]);//不取走 
					for1(k,l,r-1)
						dp[l][r][x][y]=min(dp[l][r][x][y],dp[l][k][x][y]+ans[k+1][r]);//把k+1到r取走 
				}
			for1(x,1,m)	
				for1(y,x,m)
					ans[l][r]=min(ans[l][r],dp[l][r][x][y]+aa+bb*(b[y]-b[x])*(b[y]-b[x]));
		}
	}
	printf("%lld",ans[1][n]);
	return 0;
}