题解 P3648 【[APIO2014]序列分割】

· · 题解

另一种斜率优化(式子不太一样)

显然，我是蒟蒻，所以不知道怎么记贡献，所以我选择每一次直接记录答案

对于每一次从j转移到i增加的答案为 (sum[n] - sum[i])(sum[i] - sum[j])

这十分的直观(按题意模拟),所以我不想解释。

于是可以斜率优化：

-\frac{dp[j]-dp[k]}{sump[j] - sump[k]}>=sum[i] - sum[n]

由于推式子的过程只用到了初一数学，我也不再赘述

然后就可以套路DP了,

由于蒟蒻我不会滚动数组等骚操作，于是就有了一下这些很烂的代码，

#include<bits/stdc++.h>
using namespace std;

long long line[100005];
long long dp  [100005][205];

int j;

long double Y(int now){ return dp[now][j];}
long double X(int now){ return line[now] ;}
long double K(int x,int y){ if(X(x) == X(y))return -1e18;return - ( Y(x) - Y(y) ) * 1.0 / ( X(x) - X(y) ) ;}

int head[305];
int tail[305];
int Q  [305][100005];
int pre[100005][305];
int main(){
    int n,k;cin >> n >> k;
    for(int i = 1;i <= n;i ++)cin >> line[i],line[i] += line[i - 1];
    for(int i = 1;i <= n;i ++){
        for(j = 0;j < k;j ++){
            while( head[j] < tail[j] and K( Q[j][head[j]],Q[j][head[j] + 1]) <= line[i] - line[n] )head[j] ++;
            int ft = Q[j][head[j]];
            dp [i][j + 1] = dp[ft][j] + (line[n] - line[i])*(line[i] - line[ft]);
            pre[i][j + 1] = ft;
            while( head[j] < tail[j] and K( Q[j][tail[j]-1],Q[j][tail[j]]) >= K( Q[j][tail[j]],i ) )tail[j] --;
            Q[j][++tail[j]] = i;
        }
    }
    long long ans = 0,t = 0;
    for(int i = 1;i <= n;i ++){if( dp[i][k] > ans )ans = dp[i][k],t = i; }
    cout << ans << "\n";
    stack<int>A;
    for(int i = k;i >= 1;i --){
        A.push(t);
        t = pre[t][i];
    }
    while(!A.empty())cout << A.top() << " ",A.pop();
    return 0;
}

Tips: