题目描述
在一根数轴上，你将依次放入 \(N\) 根长度为 \(d_i\) 的线段。
每次，你可以将线段放置于数轴上并使得其中一段等于上一段的末尾。假设上一次的末尾为 \(x\)，则这次你可以将线段置于 \([x-d,x]\) 或 \([x,x+d]\)，并将 \(x\) 设为 \(x-d\) 或 \(x+d\)。
求最终摆出的的·线段长度并最小值。
思路
令 \(dp_{i,j}\) 表示考虑前 \(i\) 根线段，上一次的末尾离左端点的距离为 \(j\) 时离右端点最近可以是多少。
很明显有转移：
\[\begin{array}{l} dp_{i+1,j+d_{i+1}}\leftarrow \max(0,dp_{i,j}-d_{i+1})\\ dp_{i+1,\max(0,j-d_{i+1})}\leftarrow dp_{i,j}+d_{i+1} \end{array} \]但这里的 \(j\) 有多大呢？
你可能会想到 \(1000\)，毕竟最大线段长度就 \(1000\)。
但如果当前是右端点，接着依次出现一个 \(500,1000\)，此时就无法做到不超过右端点，即 \(j>1000\)。
但实际上 \(j\le 2000\)，因为只要有一个长度为 \(2000\) 的区间，在里面怎么跳都是不会越界的。
时空复杂度均为 \(O(N\max\{d_i\})\)。
代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 10001, MAXV = 2001;
int t, n, a[MAXN], dp[MAXN][MAXV], ans;
void Solve() {
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
}
for(int i = 0; i <= n; ++i) {
for(int j = 0; j <= 2000; ++j) {
dp[i][j] = 114514;
}
}
dp[0][0] = 0;
ans = 114514;
for(int i = 0; i < n; ++i) {
for(int j = 0; j <= 2000; ++j) {
if(j + a[i + 1] <= 2000) {
dp[i + 1][j + a[i + 1]] = min(dp[i + 1][j + a[i + 1]], max(0, dp[i][j] - a[i + 1]));
}
dp[i + 1][max(0, j - a[i + 1])] = min(dp[i + 1][max(0, j - a[i + 1])], dp[i][j] + a[i + 1]);
}
}
for(int i = 0; i <= 2000; ++i) {
ans = min(ans, dp[n][i] + i);
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
for(cin >> t; t--; Solve()) {
}
return 0;
}