题目描述
小明很喜欢打游戏，现在已知一个新英雄即将推出，他同样拥有四个技能，其中三个小技能的释放时间和固定的伤害值为：
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
输入
83 12 31 33 3 3 3
输出
24
备注:
大招：蓄力时间最短L秒，最多R秒。无限次释放，释放之后照成的伤害是随着时间增加的 蓄力L秒释放能够造成Temp的伤害 蓄力L+1秒释放能够造成Temp+1*A的伤害 依次类推
题解
完全背包，$dp$，单调队列优化。
针对前三种技能，可以做完全背包来解决，对于第四种技能，如果暴力$dp$，需要枚举$[L,R]$，复杂度爆炸，可以用单调队列优化。
注意：不可以用斜率优化，之前用斜率优化能AC，现在发现是错误的！
#includeusing namespace std;const int maxn = 1e5 + 10;int T;long long x, a;long long y, b;long long z, c;int L, R;long long temp, A;long long dp[maxn];int q[maxn];int first, last;bool check1(int X, int Y) { if((dp[Y] - dp[X]) > A * (Y - X)) return 1; return 0;}int main() { while(~scanf("%d", &T)) { for(int i = 0; i <= T; i ++) { dp[i] = 0; } scanf("%lld%lld", &x, &a); scanf("%lld%lld", &y, &b); scanf("%lld%lld", &z, &c); scanf("%d%d%lld%lld", &L, &R, &temp, &A); for(int i = x; i <= T; i ++) { dp[i] = max(dp[i], dp[i - x] + a); } for(int i = y; i <= T; i ++) { dp[i] = max(dp[i], dp[i - y] + b); } for(int i = z; i <= T; i ++) { dp[i] = max(dp[i], dp[i - z] + c); } first = last = 0; q[first] = 0; for(int i = L; i <= T; i ++) { while(1) { if(last - first + 1 < 1) break; if(i - q[first] > R) first ++; else break; } dp[i] = max(dp[i], dp[q[first]] + temp + A * (i - L - q[first])); dp[i] = max(dp[i - 1], dp[i]); while(1) { if(last - first + 1 < 1) break; if(!check1(q[last], i - L + 1)) break; last --; } last ++; q[last] = i - L + 1; } printf("%lld\n", dp[T]); } return 0;}