ABC163E Active Infants 做题记录

给定 $n$ 个数 $a_{[1,n]}$，现在要将其重排。

如果 $a_i$ 于重排前在第 $i$ 个位置，现在移动到了第 $j$ 个位置，那么对答案的贡献就是 $|j-i|\times a_i$。

输出所有重排方案中最大的答案。

• $2 \leq N \leq 2000$
• $1 \leq A_i \leq 10^9$

首先不难发现最大值一定是放在 $1$ 或者 $n$，但是会出现放在 $1$ 和 $n$ 时价值相同的情况，所以不能直接贪心。

那么考虑设 $dp_{l,r}$ 表示重新排列 $a_{[l,r]}$ 后这段区间对答案的最大贡献，但是似乎不太好转移。

继续挖掘性质，不难发现原来的顺序并不重要，考虑从小到大填数。设 $dp_{l,r}$ 表示前 $r-l+1$ 小的数填入 $[l,r]$ 后对答案的最大贡献，转移：

$dp_{[l,r]}=\max(dp_{[l,r-1]}+|pos_{r-l+1}-r|\times val_{r-l+1},dp_{[l+1,r]}+|pos_{r-l+1}-l|\times val_{r-l+1})$

其中 $pos_i$ 和 $val_i$ 分别表示 $a$ 中第 $i$ 小的数的位置和数值。

边界为 $dp_{i,i-1}=0$，答案为 $dp_{1,n}$。

代码如下：

// Problem: [ABC163E] Active Infants
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT_abc163_e
// Memory Limit: 1 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int S=2005;

int n,a[S];
int id[S];
long long dp[S][S];

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),id[i]=i;
	sort(id+1,id+n+1,[&](int x,int y){return a[x]<a[y];});
	for(int len=1;len<=n;len++)
	{
		for(int l=1;l<=n-len+1;l++)
		{
			int r=l+len-1;
			dp[l][r]=max(
				dp[l][r-1]+1ll*abs(id[r-l+1]-r)*a[id[r-l+1]],
				dp[l+1][r]+1ll*abs(id[r-l+1]-l)*a[id[r-l+1]]
			);
		}
	}
	printf("%lld\n",dp[1][n]);
	return 0;
}