首页 > 代码库 > [Vijos1617] 超级教主（DP + 单调队列）
[Vijos1617] 超级教主（DP + 单调队列）
传送门
设 f[i] 表示吃完 f[i] 及其以下的能量球后所剩下的能量。
所以 f[i] = max(f[i], f[j] + (sum[i] - sum[j]) - i * 100) ( 0 <= j < i )
但这是 O(n2) 的，肯定超时，
把上面的式子变换以下得到 f[i] = max(f[i], (f[j] - sum[j]) + sum[i] - i * 100) ( 0 <= j < i )
也就是说，f[i] 只与 f[j] - sum[j] 有关，sum[i] - i * 100 可看做常数，
要想使 f[i] 最大，需要让 f[j] - sum[j] 最大，
可用单调队列维护最大 f[j] - sum[j]，
如果 f[q[h]] < i * 100 说明能量不够跳到当前点，而能量跳不到当前点肯定也跳不到后面的点，h++
——代码
1 #include <cstdio> 2 3 const int MAXN = 2000001; 4 int n, m, h = 1, t; 5 int sum[MAXN], q[MAXN], f[MAXN]; 6 7 int main() 8 { 9 int i, j, x;10 scanf("%d %d", &n, &f[0]);11 for(i = 1; i <= n; i++)12 {13 scanf("%d", &x);14 sum[i] = x + sum[i - 1];15 }16 t++;17 for(i = 1; i <= n; i++)18 {19 while(h <= t && f[q[h]] < i * 100) h++;20 f[i] = f[q[h]] - sum[q[h]] + sum[i] - i * 100;21 while(h <= t && f[q[t]] - sum[q[t]] < f[i] - sum[i]) t--;22 q[++t] = i;23 }24 printf("%d", f[n]);25 return 0;26 }
[Vijos1617] 超级教主（DP + 单调队列）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。