题目描述

本题的方法需要用动态规划来做，状态表示为f[i][j]，i表示无伤通过第i个怪兽，j表示花了j个金币，本题的金币上限是可以求出来的，j = 2 * i，f[i][j]表示顺利通过第i个怪兽，花了j个金币的情况下的获得的怪兽的最大武力值。思路很难想，我也不会。

动态规划一般可以看成是一堆方案的集合，我们需要知道的是集合的方案数或者最大值或者最小值。其实个人理解为每一步都有一堆方案的集合。本题的的状态表示的该集合中的最大值。

第二点需要明白的是状态转移，本题的状态转移有两块，买还是不买，但是不买需要有条件，就是前面买下的怪兽的总武力值需要大于等于（不要忘了等于）当前怪兽的武力值。

结果就是通过N个怪兽所需要的最小金币数。

算法1

(动态规划) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;

typedef long long LL;

LL d[60],f[60][120];
int p[60];

int main()
{
    int N;
    cin >> N;
    for(int i = 1; i <= N; i ++ ) cin >> d[i];
    for(int i = 1; i <= N; i ++ ) cin >> p[i];

    memset(f, -1, sizeof f);
    f[0][0] = 0;

    for(int i = 1; i <= N; i ++ )
        for(int j = 1; j <= N * 2; j ++ )
        {
            if(j >= p[i] && f[i - 1][j - p[i]] != -1) f[i][j] = f[i - 1][j - p[i]] + d[i];
            if( f[i - 1][j] >= d[i])  f[i][j] = max(f[i][j], f[i - 1][j]);
        }

    int res = 0;
    for(int i = 1; i <= 2 * N; i ++ )
        if(f[N][i] != -1) {
            res = i;
            break;
        }

    cout << res << endl;

    return 0;
}