SRM 563 Div1 500 SpellCards

Description

有n张符卡排成一个队列，每张符卡有两个属性，等级lili和伤害didi。

你可以做任意次操作，每次操作为以下二者之一：

把队首的符卡移动到队尾。
使用队首的符卡，对敌人造成di点伤害，并丢弃队首的li张符卡（包括你所使用的符卡）。如果队列不足li张符卡那么你不能使用。

求出造成的伤害的总和的最大值。

\(1\len\le50,1\leli\le50,1\ledi\le10000\)

Solution

发现这就是一个背包问题

Code

#include <algorithm>

#include <stdio.h>

#include <vector>

using namespace std;

class SpellCards {

    int f[105];

  public:

    int maxDamage(vector<int> l, vector<int> d) {

        int n = l.size();

        for (int i = 0; i < n; i += 1)

            for (int j = n; j >= l[i]; j -= 1)

                f[j] = max(f[j], f[j - l[i]] + d[i]);

        return *max_element(f + 1, f + n + 1);

    }

};

巴特西

SRM 563 Div1 500 SpellCards

Description

Solution

Code

最新文章

热门文章