题目描述

blablabla

算法1

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

类似背包问题，每次更新遇到第i个怪兽后，花费j枚硬币能获取的最大武力值，更新状态时需要分2类，即当前武力值大于这个怪，或者当前武力值小于这个怪。当武力值大于这个怪，更新j+p[i]即任然买下此怪兽，战斗力是否上升；取最大战斗力

最后从0个硬币往后枚举，看每种情况对应的武力值是否为0；不为0即可以通关

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 60;
long long d[N];
int p[N];
long long dp[N][2*N];

int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> d[i];
    for(int i = 0; i < n; i++) cin >> p[i];;
    for(int i = p[0]; i < 2*N; i++) dp[0][i] = d[0];

    for(int i = 1; i < n; i++)
    {
        for(int j = 0; j <= 2*n; j++)
        {
            if(dp[i-1][j] < d[i])
            {
                if(dp[i-1][j] != 0)dp[i][j+p[i]] = max(dp[i-1][j]+d[i], dp[i][j+p[i]]);
                if(j-p[i]>=0 && dp[i-1][j-p[i]]!=0)dp[i][j] = max(dp[i-1][j-p[i]]+d[i], dp[i][j]);
                else
                    dp[i][j] = 0;
                //
            }
            else
            {
                dp[i][j] = max(dp[i-1][j],dp[i][j]);
                dp[i][j+p[i]] = max(dp[i-1][j]+d[i], dp[i][j+p[i]]);
            }
            //cout << dp[i][j] <<" ";
        }
        //cout << endl;
    }
    int k = 0;
    while(dp[n-1][k] == 0)k++;
    cout << k << endl;
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla