SRM563 Div1 500 SpellCards

发表于 | 分类于

Description

有\(n\)张符卡组成的队列，第\(i\)张有权值\(l_i\)和伤害\(d_i\)。每次你可以把队首的卡扔到队尾，也可以发动队首的卡，发动后会对对方造成\(d_i\)点伤害，但是要将从这张卡开始的\(l_i\)张除外（因此如果队列中卡不足\(l_i\)张就不能发动此卡）。最大化伤害。

\(1\leq n,l_i\leq 50\)。

Solution

各位兄贵可能一看就觉得事环上DP罢（正论）

但这题只需要背包（一转）

如果有一个卡组子集，满足\(l_i\)之和不大于\(n\)，那么这个集合一定可以打出来。然后很显然的是\(l_i\)和大于\(n\)的话肯定没法全发动，因此背包就行辣……

觉得这个很玄学？那可以考虑证明一下呢……

我们不妨记在集合中的卡为黑卡，不在集合中的卡为白卡。在经过一定的移动之后，序列一定会变成若干段一张黑卡跟几张白卡的序列（并且满足开头没有白卡）。首先我们注意到，如果有一个黑卡\(i\)之后跟的白卡数量不小于\(l_i - 1\)的话，一定可以经过一定移动后发动这张卡。

那么问题来了，对于当前局面，是否可能会出现一张卡都发动不了的情况？

答案是否定的，因为这样就意味着每个黑卡及其后面跟的白卡加起来小于\(l_i\)，也就是说这若干段的总卡数竟然小于\(n\)！我们在发动一张卡之后，\(l_i\)的和下降的值和\(n\)下降的值是一样的，因此一定可以接着往下发动，将所有黑卡发动完。

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
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
int f[50];
struct SpellCards {
  void pack(int n, int l, int d) {
    for(int i = n; i >= l; i --) {
      f[i] = std::max(f[i], f[i - l] + d);
    }
  }
public:
  int maxDamage(std::vector<int> level, std::vector<int> damage) {
    memset(f, 0, sizeof(f));
    int s = level.size();
    for(int i = 0; i < s; i ++) {
      pack(s, level[i], damage[i]);
    }
    return *std::max_element(f, f + 1 + s);
  }
};

#ifdef LOCAL
int main() {
  int n; scanf("%d", &n);
  std::vector<int> A, B;
  for(int i = 0; i < n; i ++) {
    int x; scanf("%d", &x);
    A.push_back(x);
  }
  for(int i = 0; i < n; i ++) {
    int x; scanf("%d", &x);
    B.push_back(x);
  }
  SpellCards solver;
  printf("%d\n", solver.maxDamage(A, B));
  return 0;
}
#endif