这个数据范围让我们不得不往背包想。
但是两维相互限制。考虑坐标系旋转 \(45°\),转化为两维不相互限制。
那我们现在相当于要安排正负号,使得 \(\sum\limits_{i = 1}^n \pm d_i\) 等于一个给定的值 \(K\)。
考虑两边加上 \(\sum\limits_{i = 1}^n d_i\) 并除以 \(2\),转化为纯粹的 01 背包问题。
bitset 优化即可。时间复杂度 \(O(\frac{n \sum\limits_{i = 1}^n d_i}{w})\)。
code
// Problem: G - Jumping sequence
// Contest: AtCoder - AtCoder Beginner Contest 221
// URL: https://atcoder.jp/contests/abc221/tasks/abc221_g
// Memory Limit: 1024 MB
// Time Limit: 5000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 2020;
const int maxm = 3600100;
int n, A, B, a[maxn], b[maxn];
bitset<maxm> f[maxn];
void solve() {
scanf("%d%d%d", &n, &A, &B);
int s = 0;
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
s += a[i];
}
int x = A - B, y = A + B;
A = x;
B = y;
if (((A + s) & 1) || ((B + s) & 1)) {
puts("No");
return;
}
A = (A + s) / 2;
B = (B + s) / 2;
if (A < 0 || B < 0) {
puts("No");
return;
}
f[0][0] = 1;
for (int i = 1; i <= n; ++i) {
f[i] = (f[i - 1] << a[i]) | f[i - 1];
}
if (!f[n].test(A) || !f[n].test(B)) {
puts("No");
return;
}
puts("Yes");
for (int i = n; i; --i) {
if (!f[i - 1].test(A)) {
A -= a[i];
b[i] |= 2;
}
if (!f[i - 1].test(B)) {
B -= a[i];
b[i] |= 1;
}
}
for (int i = 1; i <= n; ++i) {
putchar(b[i] == 0 ? 'L' : (b[i] == 1 ? 'U' : (b[i] == 2 ? 'D' : 'R')));
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Beginner sequence AtCoder Contest Jumpingbeginner sequence atcoder contest sequence atcoder jumping 221g contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 334 beginner atcoder contest 332 beginner atcoder contest 328