[ARC178C] Sum of Abs 2 题解

题意：给定 \(n\) 和 \(L\) 以及 \(n\) 个数 \(a_i\)。对于每个 \(1 \le i \le n\)，求出一个长度为 \(L\) 的 \(b\) 序列满足：\(\sum_{i=1}^{L-1}\sum_{j=i+1}^{L} |b_j-b_i|=a_i\)，并最小化 \(b\) 中的最大值。

显然 \(b\) 中元素的顺序不影响原式的结果，所以我们可以假定 \(b\) 是不降的。

那么原式可以化简为 \(\sum_{k=1}^{L-1}k \times(L-k)\times (b_{k + 1}-b_{k})\)。

设 \(c_i=b_{i+1}-b_{i}\)。会发现 \(b_1=0\)，那么原问题就变为了求一个长度为 \(L-1\) 的序列 \(c\) 满足 \(\sum_{k=1}^{L-1}k\times (L-k) \times c_k=a_i\) 并且最小化 \(\sum_{k} c_k\)。

这可以用背包 dp 来解决。因为 $k\times (L-k) \le V $，所以 \(k\) 是 \(\sqrt{V}\) 级别的，总时间复杂度 \(O(V \sqrt{V})\)。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
int n,l,a[MAXN],dp[MAXN];
signed main() {
	memset(dp,0x3f,sizeof dp);
	cin >> n >> l;
	dp[0] = 0;
	for(int k = 1;k * (l - k) <= 200000 && k <= l - 1;k++) 
		for(int i = k * (l - k);i <= 200000;i++)
			dp[i] = min(dp[i],dp[i - k * (l - k)] + 1);
	for(int i = 1;i <= n;i++) 
		cin >> a[i],
		cout << (dp[a[i]] > 1e9 ? -1 : dp[a[i]]) << endl;
	return 0;
}