TopCoder 12329 SpellCards

题目可以转化为01背包。

将level视为体积，damage视为价值，进行容量为n的01背包。

关于证明，任何一个我们选择要使用的卡片序列，将其倒序使用，如果这些卡片的level之和小于等于n，那么每一张卡片的使用一定不会影响到其他卡片的使用。

#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
using std::cin;
using std::cout;
using std::endl;
int f[100];

class SpellCards
{
  public:
    int maxDamage(std::vector<int> level, std::vector<int> damage)
    {
        memset(f, 0, sizeof(f));
        int n = level.size();
        for (int i = 0; i < n; i++)
        {
            for (int j = n; j >= level[i]; j--)
            {
                f[j] = std::max(f[j], f[j - level[i]] + damage[i]);
            }
        }
        return *std::max_element(f, f + 1 + n);
    }
};
#ifdef DEBUG
int main()
{
    int n;
    cin >> n;
    std::vector<int> level, damage;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        level.push_back(x);
    }
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        damage.push_back(x);
    }
    cout << SpellCards().maxDamage(level, damage);
    return 0;
}
#endif