Luogu 比赛记录
【LGR-206-Div.3】洛谷基础赛 #17 & Diligent-OI Round 1
P11274 「Diligent-OI R1 D」DlgtTemplate
周日被同机房大佬叫去写的
因为看着很dp，所以往dp想。
发现从前向后dp很神秘，后效性很大。
于是 唐了15min 想到倒序dp。
设 \(f_{i, j}\) 表示 \([i, n]\) 中选出的需要把前面所选的 \(j\) 个元素的最大值。
\(f_{i, j} \leftarrow \max(f_{i + 1, j - b_i} + a_i, f_{i, j})\)。就很没有后效性。
于是我就开始犯错了。
首先，设 \(psz_i\) 表示 \([1, i]\) 中 \(b_i = 0\) 的个数。
显然对于 \(f_{i, j}\)，仅当 \(psz_{i - 1} \ge j\) 时能取到。否则要删去的数会大于 \(j\)。而我首先想的是 \(j < i\) 即可……
其次，我过不了样例 \(4\)，在神秘力量的帮助下，我发现，我题目看少了。 题目的有很特殊的地方。
最左边某些点会在逃过删除，而很显然逃过删除的只能是最左边的点。枚举该点，设下标为 \(i\)。
则 \(i\) 后面选择的点的 \(b_i\) 只能等于 \(0\)。否则 \(i\) 会被删。
于是就可以得出答案了。
因为算法是 \(O(n^2)\) 的，所以求方案很好求。
点击查看代码
#ifdef ONLINE_JUDGE
#else
#define FRZ_29
#endif
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <map>
typedef long long LL;
using namespace std;
void read() {}
template<typename T, typename... U> void read(T &x, U &...arg) {
x = 0; int f = 1; char ch = getchar();
while (ch > '9' || ch < '0') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
x *= f; read(arg...);
}
void write() {}
template<typename T> void write(T x) {
if (x < 0) { putchar('-'); x = -x; }
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
const int N = 3005;
#define PRINT(x) cout << #x << " = " << x << "\n"
#define LF(i, __l, __r) for (int i = __l; i <= __r; i++)
#define RF(i, __r, __l) for (int i = __r; i >= __l; i--)
int n, a[N], b[N];
LL f[N][N], f1, f2;
int psz[N], cnt, pz[N], p1, p2, p3;
bool vis[N][N];
vector<int> ans1, ans2;
int main() {
#ifdef FRZ_29
freopen("z_example.in", "r", stdin);
freopen("z_example.out", "w", stdout);
#endif
read(n);
LF(i, 1, n) read(a[i]);
LF(i, 1, n) read(b[i]);
LF(i, 1, n) {
if (i == 1) b[i] = 0;
if (b[i] == 0) pz[++cnt] = i;
psz[i] = psz[i - 1] + (b[i] == 0);
}
RF(i, n, 1) {
LF(j, 0, n) f[i][j] = f[i + 1][j];
LF(j, b[i], n) {
if (f[i][j] < f[i + 1][j - b[i]] + a[i]) {
f[i][j] = f[i + 1][j - b[i]] + a[i];
vis[i][j] = true;
}
}
}
LF(i, 1, n) {
LF(j, 0, n) {
if (psz[i - 1] >= j && f1 < f[i][j]) {
f1 = f[i][j];
p1 = i; p2 = j;
}
}
}
LL sum = 0;
RF(i, n, 1) {
if (!b[i]) {
if (a[i] > 0) sum += a[i];
} else {
if (sum + a[i] > f2) {
f2 = sum + a[i];
p3 = i;
}
}
}
if (f1 > f2) {
LF(i, 1, cnt) {
if (pz[i] < p1) ans1.push_back(pz[i]);
else break;
}
LF(i, p1, n) {
if (vis[i][p2]) {
ans1.push_back(i);
p2 -= b[i];
}
}
write(ans1.size()); puts("");
for (auto v : ans1) { write(v); putchar(' '); }
puts(""); write(f1); puts("");
} else {
LF(i, 1, n) {
if (i == p3 || (i > p3 && !b[i] && a[i] > 0)) ans2.push_back(i);
}
write(ans2.size()); puts("");
for (auto v : ans2) { write(v); putchar(' '); }
puts(""); write(f2); puts("");
}
return 0;
}
// START AT 2024 / 11 / 11 12 : 26 : 33