看到 \(n \le 400\),以及对于每个点输出答案,很容易猜到是区间 dp。
但是我们发现我们没办法记录 Snuke 选了哪些数。
考虑 Snuke 选的数,有些是暂时对 Ant 不会造成影响的,只有 Ant 能取的范围到了这个数才会。
于是 Snuke 可以跳过一些轮到它选的步数,囤到能对 Ant 造成影响再选。
于是设 \(f_{l, r, k}\) 表示选了 \([l, r]\) 的数,Snuke 囤了 \(k\) 步,也就是说它还能选 \(k\) 次。
转移大概是 \([l, r] \gets [l - 1, r], [l, r] \gets [l, r + 1]\)。讨论 \(a_{l - 1}\) 或 \(a_{r + 1}\) 是 Snuke 选还是 Ant 选即可。注意如果是 Ant 选,由题意,需要满足这个数大于另一端的数。
实现时可以写记搜。
时间复杂度 \(O(n^3)\)。
code
// Problem: E - Greedy Ant
// Contest: AtCoder - KEYENCE Programming Contest 2021
// URL: https://atcoder.jp/contests/keyence2021/tasks/keyence2021_e
// Memory Limit: 1024 MB
// Time Limit: 3000 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 = 410;
int n, a[maxn], f[maxn][maxn][maxn];
int dfs(int l, int r, int k) {
if (f[l][r][k] != -1) {
return f[l][r][k];
}
int res = 0;
if (l > 1) {
if (k) {
res = max(res, dfs(l - 1, r, k - 1) + a[l - 1]);
}
if (a[l - 1] > a[r + 1]) {
res = max(res, dfs(l - 1, r, k + 1));
}
}
if (r < n) {
if (k) {
res = max(res, dfs(l, r + 1, k - 1) + a[r + 1]);
}
if (a[r + 1] > a[l - 1]) {
res = max(res, dfs(l, r + 1, k + 1));
}
}
return f[l][r][k] = res;
}
void solve() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
mems(f, -1);
f[1][n][0] = 0;
for (int i = 0; i <= n; ++i) {
printf("%d\n", dfs(i + 1, i, 1));
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Programming KEYENCE Contest Greedy 2021programming keyence contest greedy contest programming beginner keyence programming keyence contest 2020 programming keyence contest 2019 2021 northwestern programming european contest programming beginner atcoder programming collegiate provincial contest 2021 programming collegiate acm-icpc subregional programming acm-icpc contest programming collegiate jiangsu contest