首页 > 代码库 > 洛谷 P1910 L国的战斗之间谍(水题日常)

洛谷 P1910 L国的战斗之间谍(水题日常)

题目背景

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 1210 1 111 9 17 10 12
输出样例#1:
11

说明

数据范围:

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

 

背包dp

屠龙宝刀点击就送

#include <cstdio>int dp[1500][1500],n,m,x,A[150],B[150],C[150];int max(int a,int b){return a>b?a:b;} int main(){    scanf("%d%d%d",&n,&m,&x);    for(int i=1;i<=n;i++)    scanf("%d%d%d",A+i,B+i,C+i);    for(int i=1;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]);    printf("%d",dp[m][x]);    return 0;}

 

洛谷 P1910 L国的战斗之间谍(水题日常)