【20181027T3】山河令【DP套DP】

原题

【错解】

一眼DP

哎好像能删成奇形怪状的

弃疗，主要是没时间了

【正解】

神仙DP

明显先设(f(i,j))表示把([i,j]) 取完的最小代价

然后发现转移不了，因为可以拿很多块

但是我们发现最后一次操作是可以确定的

那我们再设(g(i,j,x,y))表示([i,j])取走一部分，使得剩下的最小值为x，最大值为y的最小代价

为了方便，我们假装j没有取

这样就可以花费(a+b imes (y-x)^2)把这部分取完

(g(i,k,x,y))可以枚举前面的((i,j)),([j+1,k-1])暴力(f)转移

对于(f(i,j)),我们枚举最后一次取的右端点k，前面用(g(i,k,x,y)+a+b imes (y-x)^2),后面用(f(k+1,j))

懒得写方程了，具体看代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 55
#define INF 0x3f3f3f3f
using namespace std;
inline void update(int &x,int y)
{
	x=(x<y? x:y);
}
int f[MAXN][MAXN],g[MAXN][MAXN][MAXN][MAXN];
int w[MAXN],t[MAXN];
int n,a,b;
int main()
{
	scanf("%d%d%d",&n,&a,&b);
	for (int i=1;i<=n;i++)
		scanf("%d",&w[i]);
	for (int i=1;i<=n;i++)
		t[i]=w[i];
	sort(t+1,t+n+1);
	int m=unique(t+1,t+n+1)-t-1;
	for (int i=1;i<=n;i++)
		w[i]=lower_bound(t+1,t+m+1,w[i])-t;
	memset(f,0x3f,sizeof(f));
	memset(g,0x3f,sizeof(g));
	for (int i=1;i<=n;i++)
		g[i][i][w[i]][w[i]]=f[i+1][i]=0;
	f[1][0]=0;
	for (int i=n;i>=1;i--)
		for (int j=i;j<=n;j++)
			for (int x=1;x<=m;x++)
				for (int y=x;y<=m;y++)
				{
					if (g[i][j][x][y]==INF) continue;
					for (int k=j+1;k<=n;k++)
						update(g[i][k][min(x,w[k])][max(y,w[k])],g[i][j][x][y]+f[j+1][k-1]);
					for (int k=j;k<=n;k++)
						update(f[i][k],g[i][j][x][y]+f[j+1][k]+a+b*(t[y]-t[x])*(t[y]-t[x]));
				}
	printf("%d
",f[1][n]);
	return 0;
}