10.29【A】

小辰的圣剑

就是说如果要出战，那么至少需要击杀一个怪物

然后有n天，每天会有ai血量的怪物

总合不得超过m

收益不得超过u

所谓最长连续天数，就是连续子数组

定义DP【i】为以i为最后一天时，声望不超过ui且不超过耐久的最大连续天数

但如果这样的话，如何状态转移？dp[i+1]应该是不能利用dp[i]的

是个线性规划的问题，即要求最大化连续的长度，即maxj-i+1

然后约束是∑i,j(ak)<m和∑i,j(bk)<u

错解&订正

由于n比较小，直接枚举貌似也不是不可行，

即维护两个数组，一个表示a的前缀和，一个是b的前缀和

然后外层枚举起点i，内层枚举j，检查合法的

内层从大向小的枚举，因为有负的存在，而且是为了寻找最大，所以一旦找到第一个合法的，那后面的就都可以不用再看了

DEBUG

正确做法

就是说从左向右枚举，一旦遇到超过了u约束，那么后面的都无法满足条件，直接在此处截断

正是因为有负权的存在

AI题解（未看）

解法一：二分答案 + 滑动窗口 + 单调队列

解法二：对每个左端点 ll，用 RMQ/线段树找最远右端点

RMQ是什么？