[BZOJ4897][Thu Summer Camp2016]成绩单

试题描述

期末考试结束了，班主任L老师要将成绩单分发到每位同学手中。L老师共有n份成绩单，按照编号从1到n的顺序叠放在桌子上，其中编号为i的成绩单分数为w_i。成绩单是按照批次发放的。发放成绩单时，L老师会从当前的一叠成绩单中抽取连续的一段，让这些同学来领取自己的成绩单。当这批同学领取完毕后，L老师再从剩余的成绩单中抽取连续的一段，供下一批同学领取。经过若干批次的领取后，成绩单将被全部发放到同学手中。然而，分发成绩单是一件令人头痛的事情，一方面要照顾同学们的心理情绪，不能让分数相差太远的同学在同一批领取成绩单；另一方面要考虑时间成本，尽量减少领取成绩单的批次数。对于一个分发成绩单的方案，我们定义其代价为：

其中，k是方案中分发成绩单的批次数，对于第i批分发的成绩单，〖max〗_i是最高分数，〖min〗_i是最低分数。a,b是给定的评估参数。现在，请你帮助L老师找到代价最小的分发成绩单的方案，并将这个最小的代价告诉L老师。当然，分发成绩单的批次数k是由你决定的。

输入

第一行包含一个正整数n，表示成绩单的数量。

第二行包含两个非负整数a,b，表示给定的评估参数。

第三行包含n个正整数w_i，表示第i张成绩单上的分数。

输出

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

输入示例

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

输出示例

数据规模及约定

n<=50, a<=100, b<=10, w_i<=300

题解

区间 dp。先将权值离散。设 f(l, r, a, b) 表示对于序列的 [l, r] 段，最终剩下的数的权值都在 [a, b] 范围内所需要的最小代价，特别地，f(l, r, 0, 0) 表示 [l, r] 中都取光的最小代价。转移时我们从 [l, r] 区间往里缩，贪心地将两边权值在 [a, b] 范围内的数丢在一边，假设我们缩到了区间 [tl, tr]，那么 f(l, r, a, b) = min{ f(tl, tr, 0, 0), f(tl, k, 0, 0) + f(k+1, tr, a, b), f(tl, k, a, b) + f(k+1, tr, 0, 0), f(tl, k, a, b) + f(k+1, tr, a, b) | k∈[tl, tr) }，然后 f(l, r, 0, 0) = min{ f(l, r, a, b) + A + B * (b - a)² | a ≤ b, a,b∈权值集 }（这里的 A 和 B 分别对应题面中的 a 和 b）。

这样设计状态的思路很像 UVA（算法竞赛入门经典）上的一道题，貌似叫“方块消除”。。。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;

int read() {
	int x = 0, f = 1; char c = getchar();
	while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
	while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
	return x * f;
}

#define maxn 55
#define oo 2147483647

int n, A, B, sco[maxn], num[maxn], f[maxn][maxn][maxn][maxn];
void up(int& a, int b) {
	a = min(a, b);
	return ;
}

int main() {
	n = read(); A = read(); B = read();
	for(int i = 1; i <= n; i++) num[i] = sco[i] = read();
	
	sort(num + 1, num + n + 1);
	int m = unique(num + 1, num + n + 1) - num - 1;
	for(int i = 1; i <= n; i++) sco[i] = lower_bound(num + 1, num + m + 1, sco[i]) - num;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			for(int a = 0; a <= m; a++)
				for(int b = 0; b <= m; b++) f[i][j][a][b] = oo;
	for(int len = 1; len <= n; len++)
		for(int l = 1; l + len - 1 <= n; l++) {
			int r = l + len - 1;
			for(int a = 1; a <= m; a++)
				for(int b = a; b <= m; b++) {
					int tl = l, tr = r;
					while(a <= sco[tl] && sco[tl] <= b) tl++;
					while(a <= sco[tr] && sco[tr] <= b) tr--;
					if(tl > tr) f[l][r][a][b] = 0;
					else if(tl == tr) up(f[l][r][a][b], A);
					else {
						for(int i = tl; i < tr; i++) {
							if(f[tl][i][a][b] < oo && f[i+1][tr][0][0] < oo)
								up(f[l][r][a][b], f[tl][i][a][b] + f[i+1][tr][0][0]);
							if(f[tl][i][0][0] < oo && f[i+1][tr][a][b] < oo)
								up(f[l][r][a][b], f[tl][i][0][0] + f[i+1][tr][a][b]);
							if(f[tl][i][a][b] < oo && f[i+1][tr][a][b] < oo)
								up(f[l][r][a][b], f[tl][i][a][b] + f[i+1][tr][a][b]);
						}
						if(f[tl][tr][0][0] < oo) up(f[l][r][a][b], f[tl][tr][0][0]);
					}
					if(f[l][r][a][b] < oo) up(f[l][r][0][0], f[l][r][a][b] + A + B * (num[b] - num[a]) * (num[b] - num[a]));
				}
		}
	
	printf("%d
", f[1][n][0][0]);
	
	return 0;
}