P10111 [GESP202312 七级] 纸牌游戏 题解

1
// Problem: P10111 [GESP202312 七级] 纸牌游戏
2
// Contest: Luogu
3
// URL: https://www.luogu.com.cn/problem/P10111
4
// Memory Limit: 512 MB
5
// Time Limit: 1000 ms
6
//
7
// Powered by CP Editor (https://cpeditor.org)
8

9
/*Code by Block_Fish*/
10
#include <bits/stdc++.h>
11

12
#define log printf
13
#define EPS 1e-8
14
#define INF 0x3f3f3f3f
15
#define FOR(i, l, r) for (int(i) = (l); (i) <= (r); ++(i))
16
#define IOS                      \
17
  ios::sync_with_stdio(false); \
18
  cin.tie(nullptr);            \
19
  cout.tie(nullptr);
20

21
using namespace std;
22

23
typedef __int128 i128;
24
typedef long long ll;
25
typedef pair<int, int> PII;
26

27
const int N = 1010;
28
int n, a[N], b[N], c[N], dp[3][N], ans = -INF;
29

30
template <typename T>
31

32
inline T read() {
33
  T sum = 0, fl = 1;
34
  char ch = getchar();
35
  for (; !isdigit(ch); ch = getchar())
36
    if (ch == '-') fl = -1;
37
  for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
38
  return sum * fl;
39
}
40

41
template <typename T>
42

43
inline void write(T x) {
44
  if (x < 0) putchar('-'), write<T>(-x);
45
  static T sta[35];
46
  int top = 0;
47
  do { sta[top++] = x % 10, x /= 10; } while (x);
48
  while (top) putchar(sta[--top] + 48);
49
}
50

51
int pk(int x, int y) {
52
  if (x == y) return 1;
53
  if (x == y + 1 || x == y - 2) return 2;
54
  return 0;
55
}
56

57
int main() {
58
  n = read<int>();
59
  FOR(i, 1, n) a[i] = read<int>();
60
  FOR(i, 1, n - 1) b[i] = read<int>();
61
  FOR(i, 1, n) c[i] = read<int>();
62
  memset(dp, -0x3f, sizeof(dp));
63
  FOR(i, 0, 2) dp[i][0] = pk(i, c[1]) * a[1];
64
  FOR(i, 2, n)
65
  for (int j = i - 1; j >= 0; --j) FOR(k, 0, 2) {
66
      int s = pk(k, c[i]) * a[i];
67
      dp[k][j] += s;    // 默认不换
68
      if (j > 0)      // 防止越界
69
        FOR(l, 0, 2)  // 换，换成 l
70
      dp[k][j] = max(dp[k][j], dp[l][j - 1] + s - b[j]);
71
    }
72
  FOR(i, 0, n - 1)
73
  FOR(j, 0, 2) ans = max(ans, dp[j][i]);
74
  log("%d", ans);
75
  return 0;
76
}