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;
}