[f[i] = f[j] + (i – j – 1) * (i – j) /2 + a[i] ]
[f[j] + j * (j + 1) / 2 = i * j + f[i] – a[i] – i * (i – 1) / 2 ]
[Y(f[j] + j * (j + 1) / 2 ) = k(i) X(j) + b(f[i] – a[i] – i * (i – 1) / 2) ]
const int N = 1e6 + 10;
int n, a[N], f[N];
int q[N], hh = 1, tt = 1;
inline int X(int i){ return i; }
inline int Y(int i){ return f[i] + (i * i + i) / 2; }
inline double slope(int i, int j){
return (double)(Y(i) - Y(j)) / (X(i) - X(j));
}
signed main(){
read(n);
for(int i = 1; i slope(q[tt], i)) -- tt;
q[++ tt] = i;
}
print(f[n]);
return 0;
}
题意：对于给定序列询问区间内的最长连续值域。
Original: https://www.cnblogs.com/William-Sg/p/16436409.html
Author: Altwilio
Title: [暑期考试]2022.7.1
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/604050/
转载文章受原作者版权保护。转载请注明原作者出处！