ABC163E Active Infants 做题记录

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

如果 aia_i 于重排前在第 ii 个位置,现在移动到了第 jj 个位置,那么对答案的贡献就是 ji×ai|j-i|\times a_i

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

  • 2N20002 \leq N \leq 2000
  • 1Ai1091 \leq A_i \leq 10^9

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

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

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

dp[l,r]=max(dp[l,r1]+posrl+1r×valrl+1,dp[l+1,r]+posrl+1l×valrl+1)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})

其中 posipos_ivalival_i 分别表示 aa 中第 ii 小的数的位置和数值。

边界为 dpi,i1=0dp_{i,i-1}=0,答案为 dp1,ndp_{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;
}