BalticOI 2009 Day1 - 甲虫

https://www.luogu.com.cn/problem/P4870

首先看到题面就能想到排序后区间 dp。

设 \(f_{i,j,0/1}\) 表示区间 \([i,j]\)，收集完毕后在哪个端点时能收集到最多的露水，但是发现转移过程中还需要这时的最小时间。如果再添加一个数组维护这时的最小时间呢？那么能够发现时间和收集到的露水数都是影响答案的因素。但是我们已经不能把这两个拿出其中塞到状态里了。

考虑把一些贡献提前计算，具体地，对于从 \(i\) 到 \(j\) 的一个转移，时间为 \(abs(x_i-x_j)\)，那么我们就应提前减掉 还未收集但将要收集的露水位置数乘上这个耗费的时间。

所以我们提前枚举计划收集的露水位置数，然后就可以 dp 了。

//P4870
#include <bits/stdc++.h>
using namespace std;

const int N = 310;
int n, m, a[N], f[N][N][2], ans;

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++ i){
		scanf("%d", &a[i]);
	}
	sort(a + 1, a + n + 1);
	for(int i = 1; i <= n; ++ i){
		memset(f, 0xcf, sizeof(f));
		for(int j = 1; j <= n; ++ j){
			f[j][j][0] = m * i - abs(a[j]) * i;
		}
		for(int le = 2; le <= i; ++ le){
			for(int l = 1; l + le - 1 <= n; ++ l){
				int r = l + le - 1, s = i - (r - l);
				f[l][r][0] = max(f[l+1][r][0]-(a[l+1]-a[l])*s, f[l+1][r][1]-(a[r]-a[l])*s);
				f[l][r][1] = max(f[l][r-1][0]-(a[r]-a[l])*s, f[l][r-1][1]-(a[r]-a[r-1])*s);
			}
		}
		for(int j = 1; j + i - 1 <= n; ++ j){
			ans = max(ans, f[j][j+i-1][0]);
			ans = max(ans, f[j][j+i-1][1]);
		}
	}
	printf("%d\n", ans);
	return 0;
}