SRM563 Div1 500 SpellCards

发表于 | 分类于

Description

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

1≤n,li≤50。

Solution

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

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

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

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

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

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

答案是否定的，因为这样就意味着每个黑卡及其后面跟的白卡加起来小于li，也就是说这若干段的总卡数竟然小于n！我们在发动一张卡之后，li的和下降的值和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