【bzoj4897】[Thu Summer Camp2016]成绩单 区间dp

2018/03/06 20:43
阅读数 11

题目描述

给你一个数列,每次你可以选择连续的一段,付出 $a+b\times 极差^2$ 的代价将其删去,剩余部分拼到一起成为新的数列继续进行此操作。求将原序列全部删去需要的最小总代价是多少。

输入

第一行包含一个正整数n,表示成绩单的数量。
第二行包含两个非负整数a,b,表示给定的评估参数。
第三行包含n个正整数w_i,表示第i张成绩单上的分数。

输出

仅一个正整数,表示最小的代价是多少。

样例输入

10
3 1
7 10 9 10 6 7 10 7 1 2

样例输出

15


题解

区间dp

对于这种删除连续一段,剩下的拼到一起的问题:把操作对应到原序列上,相当于一些要么包含要么相离的操作。

相离的情况显然是区间dp,设 $f[l][r]$ 表示将原序列的 $[l,r]$ 全部删掉所需的最小总代价。

对于包含的情况,也可以使用区间dp来解决。具体方法是:同时维护转移到一半时的状态。如下图(先删b~c再删a~d):

记录从a转移到b的状态,dp得知bc可以用某代价消掉,进而推知a转移到c的状态,继续转移到d即可。

由于极差之和最大值与最小值有关,因此离散化后设 $g[l][r][i][j]$ 表示将 $[l,r]$ 删至剩下的数最小值为 $i$ ,最大值为 $j$ 的最小代价。

那么每次dp区间 $[l,r]$ ,最后一个位置 $r$ 的转移有两种情况:

  1. 和前面的 $[l,r-1]$ 放到一起删除,这样的话 $r$ 会影响最小值与最大值,相应的有 $g[l][r][\text{min}(i,w[r])][\text{max}(i,w[r])]=g[l][r-1][i][j]$ ;
  2. 和后面的某一段 $[k+1,r]$ 作为被包含的子区间删除,这样的话枚举 $k$ ,有 $g[l][r][i][j]=g[l][k][i][j]+f[k+1][r]$ 。

处理完这个区间的 $g[l][r][][]$ 后处理 $f[l][r]$ ,显然依题意有 $f[l][r]=g[l][r][i][j]+a+b\times(j-i)^2$ 。

最后的答案就是 $f[1][n]$ 。

时间复杂度 $O(n^5)$ ,常数极小可以通过。

注意边界问题什么的。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int w[52] , v[52] , f[52][52] , g[52][52][52][52];
inline void gmin(int &x , int y)
{
	x > y ? x = y : 0;
}
int main()
{
	int n , a , b , len , i , j , k , l , r;
	scanf("%d%d%d" , &n , &a , &b);
	for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &w[i]) , v[i] = w[i];
	sort(v + 1 , v + n + 1);
	memset(f , 0x3f , sizeof(f)) , memset(g , 0x3f , sizeof(g));
	for(i = 1 ; i <= n ; i ++ ) w[i] = lower_bound(v + 1 , v + n + 1 , w[i]) - v , g[i][i][w[i]][w[i]] = 0 , f[i][i] = a;
	for(len = 2 ; len <= n ; len ++ )
	{
		for(l = 1 ; l <= n - len + 1 ; l ++ )
		{
			r = l + len - 1 , g[l][r][w[r]][w[r]] = f[l][r - 1];
			for(i = 1 ; i <= n ; i ++ )
				for(j = i ; j <= n ; j ++ )
					gmin(g[l][r][min(i , w[r])][max(j , w[r])] , g[l][r - 1][i][j]);
			for(k = l ; k < r ; k ++ )
				for(i = 1 ; i <= n ; i ++ )
					for(j = i ; j <= n ; j ++ )
						gmin(g[l][r][i][j] , g[l][k][i][j] + f[k + 1][r]);
			for(i = 1 ; i <= n ; i ++ )
				for(j = i ; j <= n ; j ++ )
					gmin(f[l][r] , g[l][r][i][j] + a + b * (v[j] - v[i]) * (v[j] - v[i]));
		}
	}
	printf("%d\n" , f[1][n]);
	return 0;
}

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部