斜率优化是单调队列优化的推广
用单调队列维护递增的斜率
参考:https://www.cnblogs.com/ka200812/archive/2012/08/03/2621345.html
以例1举例说明:
转移方程为:dp[i] = min(dp[j] + (sum[i] - sum[j])^2 + C)
假设k < j < i, 如果从j转移过来比从k转移过来更优
那么 dp[j] + (sum[i] - sum[j])^2 + C < dp[k] + (sum[i] - sum[k])^2 + C
dp[j] - dp[k] < (sum[i] - sum[k])^2 - (sum[i] - sum[j])^2
dp[j] - dp[k] < -2*sum[i]*sum[k] + sum[k]*sum[k] + 2*sum[i]*sum[j] - sum[j]*sum[j]
dp[j] - dp[k] + sum[j]*sum[j] - sum[k]*sum[k] < 2*sum[i]*(sum[j] - sum[k])
(dp[j] - dp[k] + sum[j]*sum[j] - sum[k]*sum[k]) / (sum[j] - sum[k]) < 2*sum[i]
我们观察不等式左边, 它是个斜率的形式, 自变量x为sum, 函数f(x)为dp + sum*sum
我们记这个斜率为g[j, k] = (dp[j] - dp[k] + sum[j]*sum[j] - sum[k]*sum[k]) / (sum[j] - sum[k])
说明1.如果g[j, k] < 2*sum[i] 表示对于dp[i], 从j转移过来比k更优, 反之k更优
说明2.下面我们来考虑着怎么从解集去掉多余的元素, 可以证明可能存在某些元素,无论怎样都不会是最优的,可以去掉这些多余的元素
假设k < j < i
结论:如果g[i, j] < g[j, k], 那么j可以去掉
证明:对于某个i, 如果g[i, j] < 2*sum[i], 那么i比j更优, 结论成立；
如果g[i, j] >= 2*sum[i], 那么g[j, k] > g[i, j] >= 2*sum[i], 那么k比j更优,结论成立.
证毕.
所以如果把所有g[i, j] < g[j, k]的情况中(后面斜率比前面斜率小的情况)的j都去掉, 那么我们就得到相邻两个元素的斜率递增的状况
如下图
下面来说明怎么维护这个解集:
用双端队列维护这个解集, 每次从后面加入元素时, 按照说明2的方式去掉多余元素,使的相邻元素之间构成的斜率保持单调
每次从前面找答案, 由于斜率单调递增, 所以最后一个小于2*sum[i]就是最优的解, 因为这个位置之前的g[i, j]都小于2*sum,
表示后面的比前面更优, 之后的g[i, j] 都大于2*sum, 表示前面的比后面更优, 所以这个点是极值点
又因为sum[i]也具有单调性, 所以下一个极值点的位置肯定大于等于当前极值点, 所以当前极值点之前的都可以从双端队列中移出
ps:所有说明中, k < j < i
例题1：HDU - 3507
思路：维护递增斜率g[i, j] = (dp[i] - dp[j] + sum[i]*sum[i] - sum[j]*sum[j]) / (sum[i] - sum[j])
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb emplace_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head const int N = 5e5 + ;
int a[N], n, m;
LL sum[N], dp[N];
bool g(int k, int j, LL C) {
return (dp[j]-dp[k]+sum[j]*sum[j]-sum[k]*sum[k]) <= C*(sum[j]-sum[k]);
}
bool gg(int k, int j, int i) {
return (dp[i]-dp[j]+sum[i]*sum[i]-sum[j]*sum[j])*(sum[j]-sum[k]) <= (dp[j]-dp[k]+sum[j]*sum[j]-sum[k]*sum[k])*(sum[i]-sum[j]);
}
deque<int> q;
int main() {
while(~scanf("%d %d", &n, &m)) {
for (int i = ; i <= n; ++i) scanf("%d", &a[i]), sum[i] = sum[i-]+a[i];
while(!q.empty()) q.pop_back();
q.push_back();
for (int i = ; i <= n; ++i) {
while(q.size() >= ) {
int a = q.front();
q.pop_front();
int b = q.front();
if(g(a, b, *sum[i])) ;
else {
q.push_front(a);
break;
}
}
int j = q.front();
dp[i] = dp[j] + (sum[i]-sum[j])*(sum[i]-sum[j])+m;
while(q.size() >= ) {
int b = q.back();
q.pop_back();
int a = q.back();
if(gg(a, b, i)) ;
else {
q.push_back(b);
break;
}
}
q.push_back(i);
}
printf("%lld\n", dp[n]);
}
return ;
}
例题2：HDU - 1300
思路：维护递增斜率g[i, j] = (dp[i] - dp[j]) / (sum[i] - sum[j])
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb emplace_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head const int N = + ;
int a[N], p[N], n, m, T;
LL sum[N], dp[N];
bool g(int k, int j, LL C) {
return (dp[j]-dp[k]) <= C*(sum[j]-sum[k]);
}
bool gg(int k, int j, int i) {
return (dp[i]-dp[j])*(sum[j]-sum[k]) <= (dp[j]-dp[k])*(sum[i]-sum[j]);
}
deque<int> q;
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
for (int i = ; i <= n; ++i) scanf("%d %d", &a[i], &p[i]), sum[i] = sum[i-]+a[i];
for (int i = n-; i >= ; --i) p[i] = min(p[i], p[i+]);
while(!q.empty()) q.pop_back();
q.push_back();
for (int i = ; i <= n; ++i) {
while(q.size() >= ) {
int a = q.front();
q.pop_front();
int b = q.front();
if(g(a, b, p[i])) ;
else {
q.push_front(a);
break;
}
}
int j = q.front();
dp[i] = dp[j] + (sum[i]-sum[j]+)*p[i];
while(q.size() >= ) {
int b = q.back();
q.pop_back();
int a = q.back();
if(gg(a, b, i)) ;
else {
q.push_back(b);
break;
}
}
q.push_back(i);
}
printf("%lld\n", dp[n]);
}
return ;
}
例题3：HDU - 2993
思路：论文题，维护递增的斜率，居然卡读入，没意思
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb emplace_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head const int N = 1e5 + ;
int n, k, a[N], q[N], head, tail;
double sum[N];
const int BUF = ;
char Buf[BUF],*buf=Buf;
inline void read(int &a)
{
for(a=;*buf<;buf++);
while(*buf>) a=a*+*buf++-;
}
int main() {
int tot = fread(Buf, , BUF, stdin);
while(true) {
if(buf-Buf+ >= tot) break;
read(n), read(k);
for (int i = ; i <= n; ++i) read(a[i]), sum[i] = sum[i-]+a[i];
head = tail = ;
q[tail++] = ;
double ans = ;
for (int i = k; i <= n; ++i) {
while(head+ < tail) {
int a = q[head];
head++;
int b = q[head];
if((sum[i]-sum[a])*(i-b) < (sum[i]-sum[b])*(i-a)) ;
else {
q[--head] = a;
break;
}
}
int x = q[head];
ans = max(ans, (sum[i]-sum[x])/(i-x));
x = i-k+;
while(head+ < tail) {
int b = q[tail-];
--tail;
int a = q[tail-];
if((sum[x]-sum[b])*(x-a) < (sum[x]-sum[a])*(x-b));
else {
q[tail++] = b;
break;
}
}
q[tail++] = x;
}
printf("%.2f\n", ans);
}
return ;
}
例题4：UVALive - 5097
思路：去重后发现按宽度排序后，高度递减
那么维护递增斜率：g[j, k] = (dp[j] - dp[k]) / (h[k] - h[j])
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb emplace_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head const int N = 5e4 + ;
pii a[N];
vector<pii> vc;
int n, k, h[N], w[N];
LL dp[][N];
deque<int> q[];
bool g(int id, int k, int j, LL C) {
return (dp[id][j]-dp[id][k]) <= C*(h[k+]-h[j+]);
}
bool gg(int id, int k, int j, int i) {
return (dp[id][i]-dp[id][j])*(h[k+]-h[j+]) <= (dp[id][j]-dp[id][k])*(h[j+]-h[i+]);
}
int main() {
while(~scanf("%d %d", &n, &k)) {
for (int i = ; i <= n; ++i) scanf("%d %d", &a[i].fi, &a[i].se);
sort(a+, a++n);
vc.clear();
for (int i = n; i >= ; --i) if(i == n || a[i].se > vc.back().se) vc.pb(a[i]);
reverse(vc.begin(), vc.end());
n = vc.size();
for (int i = ; i < n; ++i) w[i+] = vc[i].fi, h[i+] = vc[i].se;
for (int i = ; i <= k; ++i) while(!q[i].empty()) q[i].pop_back();
q[].push_back();
for (int i = ; i <= k; ++i) for (int j = ; j <= n; ++j) dp[i][j] = 0x3f3f3f3f3f3f3f3f;
dp[][] = ;
for (int i = ; i <= n; ++i) {
for (int j = ; j < k; ++j) {
while(q[j].size() >= ) {
int a = q[j].front();
q[j].pop_front();
int b = q[j].front();
if(g(j, a, b, w[i])) ;
else {
q[j].push_front(a);
break;
}
}
int x = q[j].front();
dp[j+][i] = min(dp[j+][i], dp[j][x] + w[i]*1LL*h[x+]);
while(q[j].size() >= ) {
int b = q[j].back();
q[j].pop_back();
int a = q[j].back();
if(gg(j, a, b, i)) ;
else {
q[j].push_back(b);
break;
}
}
q[j].push_back(i);
}
}
LL ans = 1LL<<;
for (int i = ; i <= k; ++i) ans = min(ans, dp[i][n]);
printf("%lld\n", ans);
}
return ;
}
例题5：HDU - 3045
思路：维护递增斜率：g[j, k] = (dp[j]-dp[k]+sum[k]-sum[j]+a[j+1]*j-a[k+1]*k) / (a[j+1]-a[k+1])
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb emplace_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head const int N = 4e5 + ;
int n, k;
LL a[N], sum[N], dp[N];
bool g(int k, int j, LL C) {
return dp[j]-dp[k]+sum[k]-sum[j]+a[j+]*j-a[k+]*k <= C*(a[j+]-a[k+]);
}
bool gg(int k, int j, int i) {
return (dp[i]-dp[j]+sum[j]-sum[i]+a[i+]*i-a[j+]*j)*(a[j+]-a[k+]) <= (dp[j]-dp[k]+sum[k]-sum[j]+a[j+]*j-a[k+]*k)*(a[i+]-a[j+]);
}
deque<int> q;
int main() {
while(~scanf("%d %d", &n, &k)) {
for (int i = ; i <= n; ++i) scanf("%lld", &a[i]);
sort(a+, a++n);
for (int i = ; i <= n; ++i) sum[i] = sum[i-]+a[i];
while(!q.empty()) q.pop_back();
dp[] = ;
q.push_back();
for (int i = k; i <= n; ++i) {
while(q.size() >= ) {
int a = q.front();
q.pop_front();
int b = q.front();
if(g(a, b, i)) ;
else {
q.push_front(a);
break;
}
}
int j = q.front();
dp[i] = dp[j]+sum[i]-sum[j]-a[j+]*1LL*(i-j);
if(i-k+ >= k) {
while(q.size() >= ) {
int b = q.back();
q.pop_back();
int a = q.back();
if(gg(a, b, i-k+)) ;
else {
q.push_back(b);
break;
}
}
q.push_back(i-k+);
}
}
printf("%lld\n", dp[n]);
}
return ;
}
例题6：POJ - 1180
思路：要单独算s的影响，因为有s的存在时间就不好算前缀和了，对于每次新的开始s的影响是s*suf[i]
那么就是维护递增斜率：g[j, k] = (dp[j]-dp[k]+s*(suf[j+1]-suf[k+1]) / (sum[j] - sum[k])
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<deque>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb emplace_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head const int N = 1e4 + ;
int T[N], F[N], n, s;
LL sum[N], suf[N], dp[N];
bool g(int k, int j, LL C) {
return dp[j]-dp[k]+s*(suf[j+]-suf[k+]) <= C*(sum[j]-sum[k]);
}
bool gg(int k, int j, int i) {
return (dp[i]-dp[j]+s*(suf[i+]-suf[j+]))*(sum[j]-sum[k]) <= (dp[j]-dp[k]+s*(suf[j+]-suf[k+]))*(sum[i]-sum[j]);
}
deque<int> q;
int main() {
scanf("%d", &n);
scanf("%d", &s);
for (int i = ; i <= n; ++i) scanf("%d %d", &T[i], &F[i]);
for (int i = ; i <= n; ++i) sum[i] = sum[i-] + F[i], T[i]+=T[i-];
for (int i = n; i >= ; --i) suf[i] = suf[i+] + F[i];
q.push_back();
for (int i = ; i <= n; ++i) {
while(q.size() >= ) {
int a = q.front();
q.pop_front();
int b = q.front();
if(g(a, b, T[i])) ;
else {
q.push_front(a);
break;
}
}
int j = q.front();
dp[i] = dp[j] + T[i]*(sum[i]-sum[j])+s*suf[j+];
while(q.size() >= ) {
int b = q.back();
q.pop_back();
int a = q.back();
if(gg(a, b, i)) ;
else {
q.push_back(b);
break;
}
}
q.push_back(i);
}
printf("%lld\n", dp[n]);
return ;
}
例题7：POJ - 2018
思路：同HDU-2993
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<deque>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb emplace_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head const int N = 1e5 + ;
int n, f, a[N];
LL sum[N];
deque<int> q;
bool g(int k, int j, int i) {
return (sum[j]-sum[k])*(i-j) <= (sum[i]-sum[j])*(j-k);
}
int main() {
scanf("%d %d", &n, &f);
for (int i = ; i <= n; ++i) scanf("%d", &a[i]), sum[i]=sum[i-]+a[i];
q.push_back();
LL ans = ;
for (int i = f; i <= n; ++i) {
while(q.size() >= ) {
int a = q.front();
q.pop_front();
int b = q.front();
if(g(a, b, i)) ;
else {
q.push_front(a);
break;
}
}
int x = q.front();
ans = max(ans, (sum[i]-sum[x])*/(i-x));
x = i+-f;
while(q.size() >= ) {
int b = q.back();
q.pop_back();
int a = q.back();
if(!g(a, b, x)) ;
else {
q.push_back(b);
break;
}
}
q.push_back(x);
}
printf("%lld\n", ans);
return ;
}
例题8：POJ - 3709
思路：维护递增斜率：g[j, k] = (dp[j]-dp[k]+sum[k]-sum[j]+a[j+1]*j-a[k+1]*k) / (a[j+1]-a[k+1])
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<deque>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb emplace_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head const int N = 5e5 + ;
int a[N], n, k, T;
LL sum[N], dp[N];
LL dw(int k, int j) {
return a[j+]-a[k+];
}
LL up(int k, int j) {
return dp[j]-dp[k]+sum[k]-sum[j]+a[j+]*1LL*j-a[k+]*1LL*k;
}
LL g(int k, int j, LL C) {
return up(k, j) <= C*dw(k, j);
}
LL gg(int k, int j, int i) {
return up(j, i)*dw(k, j) <= up(k, j)*dw(j, i);
}
deque<int> q;
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d %d", &n, &k);
for (int i = ; i <= n; ++i) scanf("%d", &a[i]), sum[i]=sum[i-]+a[i];
while(!q.empty()) q.pop_back();
q.push_back();
for (int i = k; i <= n; ++i) {
while(q.size() >= ) {
int a = q.front();
q.pop_front();
int b = q.front();
if(g(a, b, i));
else {
q.push_front(a);
break;
}
}
int x = q.front();
dp[i] = dp[x]+sum[i]-sum[x]-a[x+]*1LL*(i-x);
x = i-k+;
if(x >= k) {
while(q.size() >= ) {
int b = q.back();
q.pop_back();
int a = q.back();
if(gg(a, b, x)) ;
else {
q.push_back(b);
break;
}
}
q.push_back(x);
}
}
printf("%lld\n", dp[n]);
}
return ;
}
例题9：UVA - 12594
思路：维护递增斜率：g[j, k] = (dp[j]-dp[k]+sum[k]-sum[j]-k*s[k]+j*s[j]) / (j-k)，其中sum[i] = ∑(j-pos)*pos, s[i] = ∑pos
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb emplace_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head const int N = 2e4 + , M = ;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int T, n, k, pos[];
LL sum[N], s[N], dp[M][N];
char nm[N], pn[N];
deque<int> q[M];
LL up(int id, int k, int j) {
return dp[id][j]-dp[id][k]+sum[k]-sum[j]-k*s[k]+j*s[j];
}
LL dw(int k, int j) {
return j-k;
}
bool g(int id, int k, int j, LL C) {
return up(id, k, j) <= C*dw(k, j);
}
bool gg(int id, int k, int j, int i) {
return up(id, j, i)*dw(k, j) <= up(id, k, j)*dw(j, i);
}
int main() {
scanf("%d", &T);
for(int cs = ; cs <= T; ++cs) {
scanf("%s %d", pn, &k);
scanf("%s", nm+);
n = strlen(nm+);
for (int i = ; i < ; ++i) pos[pn[i]-'a'] = i;
for (int i = ; i <= n; ++i) s[i] = s[i-]+pos[nm[i]-'a'];
for (int i = ; i <= n; ++i) sum[i] = sum[i-]+(i--pos[nm[i]-'a'])*1LL*pos[nm[i]-'a'];
for (int i = ; i <= k; ++i) while(!q[i].empty()) q[i].pop_back();
dp[][] = ;
q[].push_back();
for (int i = ; i <= n; ++i) {
for (int j = ; j < k; ++j) {
while(q[j].size() >= ) {
int a = q[j].front();
q[j].pop_front();
int b = q[j].front();
if(g(j, a, b, s[i])) ;
else {
q[j].push_front(a);
break;
}
}
int x = q[j].front();
dp[j+][i] = dp[j][x]+sum[i]-sum[x]-x*(s[i]-s[x]);
}
for (int j = ; j <= k; ++j) {
while(q[j].size() >= ) {
int b = q[j].back();
q[j].pop_back();
int a = q[j].back();
if(gg(j, a, b, i)) ;
else {
q[j].push_back(b);
break;
}
}
q[j].push_back(i);
}
}
printf("Case %d: %lld\n", cs, dp[k][n]);
}
return ;
}