### 题目描述

现在absi2011拿出了x个迷你装药物(嗑药打人可耻….),准备开始与那些人打了

由于迷你装一个只能管一次,所以absi2011要谨慎的使用这些药,悲剧的是,没到达最少打败该人所用的属性药了他打人必输>.<所以他用2个药去打别人,别人却表明3个药才能打过,那么相当于你输了并且这两个属性药浪费了。

现在有n个好友,有输掉拿的经验、赢了拿的经验、要嗑几个药才能打过。求出最大经验(注意,最后要乘以5)

输入输出格式

输入格式:

第一行两个数,n和x

后面n行每行三个数,分别表示输了拿到的经验(lose[i])、赢了拿到的经验(win[i])、打过要至少使用的药数量(use[i])。

输出格式:

一个整数,最多获得的经验

输入输出样例

输入样例#1:
6 8
21 52 1
21 70 5
21 48 2
14 38 3
14 36 1
14 36 2

输出样例#1:
1060

数据范围

对于10%的数据,保证x=0

对于30%的数据,保证n<=10,x<=20

对于60%的数据,保证n<=100,x<=100, 10<=lose[i], win[i]<=100,use[i]<=5

对于100%的数据,保证n<=1000,x<=1000,0<lose[i]<=win[i]<=1000000,0<=use[i]<=1000

这道题目算是01背包的变种, 和经典01背包不同的是. 每一种物品有两种选取的方法, 一种是消耗重量(在这道题目里是药物),另外一种是什么都不消耗(也就是重量为0). 之后的都跟经典01背包一样.

但是一开始做这道题的时候却卡住了, 不知道该怎么判断这两种选取. 一开始考虑加多一层循环, 但是稍微一想就觉得不可行了. 随后想到了一种方法就是, 先找出x个药能战胜所获得最多的经验, 然后回溯找出打败的人分别是谁, 然后遍历一边 没有打败的人就加上输掉所拿的经验 但是被自己造的数据咔嚓掉了..

3 10
99 100 9
1 10 1
1 10 1

像这种情况 如果按照上面的思路做的话, 会先选择打败1号和2/3号 获得110经验 然后剩下的一个选择输掉 一共111经验

很明显 这个数据是要 1号输掉 2和3号赢掉 一共获得119经验

QAQ 所以上面说的那么多都是我做这道题的错误思路(

正确的应该想出对的状态方程为

(a为输掉所得的经验 b为赢所得的经验 c打败这个对手所需要的药)
if(j < c) 
{
   dp[j] = dp[j] + a; 因为不够药 只能含泪输掉
}
else
{
   dp[j] = max(dp[j] + a,dp[j - c] + b) 
   //如果够药就要看情况了, 看看当前是战胜得到的经验多还是输掉得到的多
}

得出这个信息以后这道题目的代码就很明显了..

#include <stdio.h>
#include <algorithm>
using namespace std;
long long read()
{
    char ch = getchar();
    int f = 1;
    long long x = 0;
    while(ch < '0' || ch > '9'){if(ch == '-')f = 0;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
    return f?x:x*-1;
}
int main()
{
    long long dp[1001] = {};
    int n = read(),m = read();

    for(int i = 0;i < n;i ++)
    {
        long long a = read(),b = read(),c = read();
        for(int j = m;j >= 0;j --)
        {
            if(j < c)
            {
                dp[j] = dp[j] + a;
            }
            else
            {
                dp[j] = max(dp[j] + a,dp[j - c] + b);
            }
        }
    }

    printf("%lld",dp[m] * 5);

    return 0;
}

其实好简单的题目, 但是硬是想不出.. 以后做dp还是要画图才行呀qwq

Categories: OIer

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Related Posts

OIer

并查集学习总结

并查集学习总结 并查集在好早之前就想学了.. 虽然是一种比较简单的数据 Read more…

OIer

归并排序学习总结 & P1309

背景 之所以突然说到归并排序,是因为P1309这道题要用到&#8230 Read more…

OIer

队列和广度优先搜索

队列(queue) 队列是什么 队列是一种特殊的线性表. 是一种先进先 Read more…