[Vijos1617] 超级教主（DP + 单调队列）

传送门

设 f[i] 表示吃完 f[i] 及其以下的能量球后所剩下的能量。

所以 f[i] = max(f[i], f[j] + (sum[i] - sum[j]) - i * 100) ( 0 <= j < i )

但这是 O(n²) 的，肯定超时，

把上面的式子变换以下得到 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++

——代码

 #include <cstdio>

 const int MAXN = ;

 int n, m, h = , t;

 int sum[MAXN], q[MAXN], f[MAXN];

 int main()

 {

     int i, j, x;

     scanf("%d %d", &n, &f[]);

     for(i = ; i <= n; i++)

     {

         scanf("%d", &x);

         sum[i] = x + sum[i - ];

     }

     t++;

     for(i = ; i <= n; i++)

     {

         while(h <= t && f[q[h]] < i * ) h++;

         f[i] = f[q[h]] - sum[q[h]] + sum[i] - i * ;

         while(h <= t && f[q[t]] - sum[q[t]] < f[i] - sum[i]) t--;

         q[++t] = i;

     }

     printf("%d", f[n]);

     return ;

 }

巴特西

[Vijos1617] 超级教主（DP + 单调队列）

最新文章

热门文章