必会算法好题之LL与CC
题目描述
小明很喜欢打游戏，现在已知一个新英雄即将推出，他同样拥有四个技能，其中三个小技能的释放时间和固定的伤害值为：
1.乌鸦坐飞机 释放时间：x 固定伤害值：a
2.蜘蛛吃耳屎 释放时间：y 固定伤害值：b
3.饿狼前进 释放时间：z 固定伤害值：c
他还有一个大招，其释放的时间是一个区间【L,R】，可以在区间内任意时间点释放出技能，其如果在L+i时刻释放技能，其能够打出的伤害值为:temp+A*i
这里temp值表示技能的基础伤害（同时也就是在时刻L释放技能的伤害值）,A是一个常数。
小明很喜欢研究连招使得在有限的时间内打出最高的伤害，现在他想要在T长度单位时间内打出最高的伤害，问这个最大伤害值。
思路：
其实只看前三个技能不难想到，这是一个dp，难点就在大招部分，释放时间是个区间，如何优化呢？其实一个比较直接的思路就是直接把区间里的每个点转化成一个物品，再注意到每个物品可以无限次使用，所以是个裸的完全背包。还是非常不错的一道题.
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e5+100;
int dp[maxn];
int w[maxn],v[maxn];
signed main()
{
int n,i,j,t,x,y,a,b,c,A,z,l,r,temp;
while(cin>>t)
{
cin>>x>>a>>y>>b>>z>>c;
cin>>l>>r>>temp>>A;
memset(dp,0,sizeof dp);
int cnt=0;
w[cnt]=x,v[cnt++]=a;
w[cnt]=y,v[cnt++]=b;
w[cnt]=z,v[cnt++]=c;
for(i=l;i<=r;i++) {
w[cnt]=i;
v[cnt++]=temp+A*(i-l);
}
int ans=0;
for(i=0;i<cnt;i++)
{
for(j=w[i];j<=t;j++)
{
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
cout<<dp[t]<<endl;
}
return 0;
} 
京东工作强度 215人发布