NC14553. 小明打联盟
描述
小明很喜欢打游戏，现在已知一个新英雄即将推出，他同样拥有四个技能，其中三个小技能的释放时间和固定的伤害值为：
1.乌鸦坐飞机 释放时间：x 固定伤害值：a
2.蜘蛛吃耳屎 释放时间：y 固定伤害值：b
3.饿狼前进 释放时间：z 固定伤害值：c
他还有一个大招，其释放的时间是一个区间【L,R】，可以在区间内任意时间点释放出技能，其如果在L+i时刻释放技能，其能够打出的伤害值为:temp+A*i
这里temp值表示技能的基础伤害（同时也就是在时刻L释放技能的伤害值）,A是一个常数。
小明很喜欢研究连招使得在有限的时间内打出最高的伤害，现在他想要在T长度单位时间内打出最高的伤害，问这个最大伤害值。
输入描述
本题包含多组数据。
输入格式为：
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
输出:
24
C++(g++ 7.5.0) 解法, 执行用时: 1711ms, 内存消耗: 2100K, 提交时间: 2022-07-30 10:29:47
#include<bits/stdc++.h>
using namespace std;
const int ii=2e5;
long long dp[ii],v[ii],w[ii];
int main(){
int n;
while(cin>>n){
memset(dp,0,sizeof(dp));
for(int i=0;i<3;i++)cin>>v[i]>>w[i];
long long l,r,te,a;
cin>>l>>r>>te>>a;
for(int i=0;i<=r-l;i++)
v[i+3]=l+i,w[i+3]=te+a*i;
for(int i=0;i<=r-l+3;i++)
for(int j=v[i];j<=n;j++)
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
cout<<dp[n]<<endl;
}
}
C++(clang++ 11.0.1) 解法, 执行用时: 1903ms, 内存消耗: 1208K, 提交时间: 2023-05-16 10:05:09
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[100005];
int main()
{ ll t;
while(cin>>t)
{memset(f,0,sizeof(f));
for(ll i=0;i<3;i++)
{ll v,w;
cin>>v>>w;
for(ll j=v;j<=t;j++)
f[j]=max(f[j],f[j-v]+w);
}
ll l,r,temp,A;
cin>>l>>r>>temp>>A;
for(ll i=0;i<=r-l;i++)
{ll v=l+i,w=temp+A*i;
for(int j=v;j<=t;j++)
f[j]=max(f[j],f[j-v]+w);
}
cout<<f[t]<<endl;
}
}