洛谷-P1910 L国的战斗之间谍

洛谷-P1910 L国的战斗之间谍

原题链接：https://www.luogu.com.cn/problem/P1910

• 题目背景
• 题目描述
• 输入格式
• 输出格式
• 输入输出样例
• 说明/提示
• C++代码

---

题目背景

L国即将与I国发动战争！！

题目描述

俗话说的好：“知己知彼，百战不殆”。L国的指挥官想派出间谍前往I国，于是，选人工作就落到了你身上。

你现在有N个人选，每个人都有这样一些数据：A（能得到多少资料）、B（伪装能力有多差）、C（要多少工资）。已知敌人的探查间谍能力为M（即去的所有人B的和要小于等于M）和手头有X元钱，请问能拿到多少资料？

输入格式

N M X

A1 B1 C1

A2 B2 C2

………………

AN BN CN

输出格式

能得到的资料总数

输入输出样例

输入 #1

3 10 12
10 1 11
1 9 1
7 10 12

输出 #1

11

说明/提示

数据范围：

1≤n≤100,1≤m≤1000, 1≤x≤1000

C++代码

#include <iostream>
using namespace std;

int dp[1005][1005];

int main() {
    int n, m, x;
    cin >> n >> m >> x;
    int a[n], b[n], c[n];
    for (int i=0; i<n; ++i)
        cin >> a[i] >> b[i] >> c[i];
    for (int i=0; i<n; ++i)
        for (int j=m; j>=b[i]; --j)
            for (int k=x; k>=c[i]; --k)
                dp[j][k] = max(dp[j][k], dp[j-b[i]][k-c[i]]+a[i]);
    cout << dp[m][x] << endl;
    return 0;
}