题意
- 给你 \(n\)
条线段，告诉你每条线段的长度。
- 你需要把它们放在一条无限长的数轴上。
- 放置需满足当前线段的起点是前一个线段的终点，特别的第一个线段的起点为
00。
也就是说，若前一个线段的终点是 \(x\),当前长度为 \(d\), 那么这个线段必须放在\([x, x+d]\) ，或者\([x-d,x]\)
思路
最小覆盖长度，考虑二分答案，\(dp_{i,j}\)表示第\(i\)个线段终点落在\(j\)的可行性，注意此时\(j\)不表示实际坐标，而是表示实际覆盖区间的相对坐标。
初始时\(dp_{0,0...mid}\)全为\(true\)，因为线段1可以放在任何坐标上，容易写出转移方程：
$ dp_{i,j} = [dp{i-1,j - d_i} * (j - d_i lim)] or
[dp_{i-1,j+d_i}*(j+d_i )$
单次check时间复杂度为\(O(n^2)\)，可用bitset优化时间，加上滚动数组优化掉第一维。
总时间复杂度为\(O(n^2log_2n)\)。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);
typedef pair<int, int> pii;
typedef long long ll;
int n, m, k, q;
bitset<N> s, mod;
void work()
{
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
auto check = [&](int lim)
{
s.reset();
mod.reset();
for (int i = 0; i <= lim; i++)
s.set(i), mod.set(i);
for (auto d : a)
s = ((s >> d) | (s << d)) & mod;
return s.any();
};
int l = 0, r = N, ans = 0, mid;
while (l <= r)
{
mid = (l + r) >> 1;
if (check(mid))
{
r = mid - 1;
ans = mid;
}
else
l = mid + 1;
}
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t --> 0)
{
work();
}
}
|