题目描述

怪兽一定的金币，怪兽就会一直护送。

依次遇见N只怪兽，每只怪兽都有自己的武力值和要“贿赂”它所需的金币数。

如果没有“贿赂”某只怪兽，而这只怪兽“武力值”又大于护送他的怪兽武力之和，这只怪兽就会攻击他。

要想成功穿越怪兽谷而不被攻击，最少要准备多少金币。

题目分析

$d_i$ 表示每只怪兽的武力值

$p_i$ 表示收买i只怪兽所需的金币数

采用动态规划的思路，遇到每个怪兽都有两个选择，贿赂或者不贿赂

状态表示

$f[i][j]$ 顺利走完前i个怪兽，只花了j个金币的所有方案的集合

数据范围 $1≤N≤50$ $1≤p_i≤2$

故 $1≤i≤50$ $1≤j≤2$

状态属性

该选择下战斗力之和最大值

状态计算

贿赂第i个怪兽
$f[i][j] = f[i - 1][j - p_i] + d_i$

不贿赂第i个怪兽
$if(f[i -1][j] >= d_i)$

$f[i][j] = f[i - 1][j] $

合起来
$f[i][j] = max(f[i - 1][j - p_i] + d_i, f[i - 1][j])$

答案表示
$f[n][1…2n]$第一个能够走完的状态，即所花金币的最小值

注意

武力值范围$1≤d_i≤10^{12}$ 所以f和d都需要用long long存储

代码示例

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

typedef long long LL;

const int N = 55;

LL f[N][N * 2], d[N]; 
int p[N]; 
int n;

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%lld", &d[i]);
    for(int i = 1; i <= n; i++) scanf("%d", &p[i]);

    memset(f, -1, sizeof f); //将每个状态置为-1，即表示该状态不合法，即该方案不现实
    f[0][0] = 0; //一个怪兽都没走过，一个金币也没有花掉，该状态下的武力值为0
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n * 2; j++)
        {
            if(f[i - 1][j] >= d[i]) f[i][j] = f[i - 1][j];   
            if(f[i - 1][j - p[i]] != -1 && j >= p[i]) f[i][j] = max(f[i][j],f[i - 1][j - p[i]] + d[i]);//前一个状态是否合法，且金币预算大于怪兽价值

        }

    int res = 0;
    for(int i = 1; i <= n * 2; i++)
    {
        if(f[n][i] != -1) //第一个合法状态即为答案
        {
            res = i;
            break;
        }
    }
    printf("%d", res);
    return 0;
}