流离之人追逐幻影

用户名：pwj666

访问量：60209

签　名：

不想总是要失去后才懂得珍惜

等　　级
排　　名	37
经　　验	13957
参赛次数	11
文章发表	110
年　　龄	23
在职情况	在职
学　　校
专　　业

　　自我简介：

TA的其他文章

【原理、题解、代码】最大公约数与最小公倍数
浏览：186

你可能喜欢

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

无限背包的一道精彩应用

　　作者: 流离之人追逐幻影　　　　发表时间：2019-10-20 18:29:47 浏览：236　|　评论：0　

原题改编：哈尔滨理工大学第七届程序设计竞赛决赛-C题
```
黑暗来袭
描述

这是人类最关键的时刻，黑暗之王带领他的黑暗大军攻击人类最重要城堡LNU,凯皇作为LNU的守护者准备迎战。

凯拥有四个技能，其中三个小技能的释放时间和固定的伤害值为：

1.正义之风  释放时间：x 固定伤害值：a

2.斩首利刃  释放时间：y 固定伤害值：b

3.恶魔审判 释放时间：z 固定伤害值：c

他还有一个大招  终极时刻，其释放的时间是一个区间【L,R】，可以在区间内任意时间点释放出技能，其如果在L+i时刻释放技能，其能够打出的伤害值为:temp+A*i，这里temp值表示技能的基础伤害（同时也就是在时刻L释放技能的伤害值）,A是一个常数。

现在他想要在T长度单位时间内打出最高的伤害，问这个最大伤害值。

输入
本题包含多组数据。

输入格式为：

x a

y b

z c

L R temp A

数据范围：

1<=T<=1e5

1<=x , y , z , L , R<=T

L<=R<= a , b ,c , temp, A<=1e5

输出
输出包含一行，输出能够打出的最高伤害值。

输入样例 1

8
3 1
2 3
1 3
3 3 3 3
输出样例 1

24
```
题解：
```
无限背包的一道应用：
将时间T看做背包容量，技能施法时间看做物品所占空间，技能伤害看做物品价值。这道题的难点在于如何处理大招，因此我们可以把大招看做两个技能，不蓄力的大招，蓄力i时间长的大招；这样就可以用dp求出这5个技能在T时间内的最高伤害了；不过上面dp可能容量没有装满就达到最大价值，即不一定用满T时间就造成了最高伤害；多出来的时间可能不够放小技能，那么多出来的时间用来放蓄力部分的大招可能会更划算。所以最后还要dp一下蓄力部分的大招。
```

AC代码：
```
#include<bits/stdc++.h>
using namespace std;
const int MAX=1e5+1e4;
long long d[MAX];
int main()
{
    long long T,x,a,y,b,z,c,L,R,temp,A;
    while(scanf("%lld",&T)!=EOF)
    {
        scanf("%lld%lld%lld%lld%lld%lld%lld%lld%lld%lld",&x,&a,&y,&b,&z,&c,&L,&R,&temp,&A);
        memset(d,0,sizeof d);
        for(long long i=1;i<=T;i++)
        {
            if(i>=x)d[i]=max(d[i],d[i-x]+a);
            if(i>=y)d[i]=max(d[i],d[i-y]+b);
            if(i>=z)d[i]=max(d[i],d[i-z]+c);
            if(i>=L)d[i]=max(d[i],d[i-L]+temp);
            if(i>=R)d[i]=max(d[i],d[i-R]+temp+A*(R-L));
        }
        for(long long i=L;i<=R;i++)d[T]=max(d[T],d[T-i]+temp+A*(i-L));
        printf("%lld\n",d[T]);
    }
    return 0;
}
```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.9 （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

无限背包的一道精彩应用

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

WU-整除问题（C++代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

完数（C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

The 3n + 1 problem （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

简单的a+b （C语言代码）

C二级辅导-等差数列（C语言代码）

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.9 （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

无限背包的一道精彩应用

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

WU-整除问题 （C++代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

完数 （C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

The 3n + 1 problem （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

简单的a+b （C语言代码）

C二级辅导-等差数列 （C语言代码）

　　评论区

WU-整除问题（C++代码）

完数（C语言代码）

C二级辅导-等差数列（C语言代码）