SDOI2016 征途

归途致敬了这道题目
本质斜率优化DP板子题
推一下式子：

---

已知：

$$s^2 = \frac{(v - v_1)^2 + (v - v_2)^2 + \cdots + (v - v_m)^2}{m}$$

然后：

$$s^2 = \frac{\left( \frac{\sum_{i=1}^m v_i}{m} - v_1 \right)^2 + \left( \frac{\sum_{i=1}^m v_i}{m} - v_2 \right)^2 + \cdots + \left( \frac{\sum_{i=1}^m v_i}{m} - v_m \right)^2}{m}$$

展开：

$$s^2 = \frac{m \times \left( \frac{\sum_{i=1}^m v_i}{m} \right)^2 - 2 \times \left( \frac{\sum_{i=1}^m v_i}{m} \right) \times (v_1 + v_2 + \cdots + v_m) + (v_1^2 + v_2^2 + \cdots + v_m^2)}{m}$$

然后可化为：

$$s^2 = \frac{m}{m} \left( \sum_{i=1}^m v_i \right)^2 - 2 \times \frac{\left( \sum_{i=1}^m v_i \right)^2}{m} + (v_1^2 + v_2^2 + \cdots + v_m^2)$$

然后：

$$s^2 = -\frac{\left( \sum_{i=1}^m v_i \right)^2}{m^2} + \frac{v_1^2 + v_2^2 + \cdots + v_m^2}{m}$$

还要 $\times m^2$

$$s^2 \times m^2 = -\left( \sum_{i=1}^m v_i \right)^2 + m \times (v_1^2 + v_2^2 + \cdots + v_m^2)$$

---

现在就可以发现，这个式子第一项是定值，只要求出第二项的右方式子的最小值。

用 $f_{i,l}$ 表示前 $i$ 段分为 $l$ 天走的最小平方和

即有：

$$f_{i,l} = \min(f_{i,l}, f_{j,l-1} + (sum_i - sum_j)^2) \quad (0 \le j < i)$$

（$m$ 可以最后乘上）

然后 80 分到手

考虑复杂度瓶颈，枚举 $i , j$ 时间复杂度 $O(n^2m)$ ，考虑压掉一个。
拆一下式子发现：

$$f_{i,l} = sum_i^2 + min(f_{j,l-1} - 2 \times sum_j \times sum_i+ sum_j^2)$$

显然，右边括号里部分是一个直线形式，其中

$$k= 2 \times sum_j$$

$$b=f_{j,l-1}+sum_j^2$$

其中斜率 $k$ 单调递减

所以用单调队列维护一个下凸壳即可。时间复杂度 $O(n)$

---

代码变量和推导不同

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
using i128 = __int128_t;
using ull = unsigned long long;

const int N = 5e3+9;          // 最大数据范围
const ll mod = 998244353;     // 模数（本题未用到）
const ll inf = 2e15;          // 无穷大，用于初始化 dp

ll a[N];                      // 原数组
ll pre[N];                    // 前缀和数组
ll dp_pre[N], dp_cur[N];      // 滚动数组：dp_pre 表示上一维（k-1 段）的 dp 值，dp_cur 表示当前维（k 段）的 dp 值

void solve(){
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        pre[i] = pre[i-1] + a[i];   // 计算前缀和
    }
    
    // 初始化：分成 1 段之前，dp_pre[i] 表示前 i 个元素分成 0 段的最小平方和
    // 只有 dp_pre[0] = 0，其余为无穷大（不可达）
    for(int i = 1; i <= n; i++) dp_pre[i] = inf;
    dp_pre[0] = 0;
    
    // k 表示当前正在计算分成 k 段的情况
    for(int k = 1; k <= m; k++){
        // 当前维 dp_cur 初始化为无穷大
        for(int i = 0; i <= n; i++) dp_cur[i] = inf;
        
        deque<int> q;   // 单调队列，维护下凸壳，存储决策点 j 的索引
        
        // add 函数：向凸壳中加入一个决策点 p 对应的直线
        // 该直线方程为 y = k*x + b，其中 k = -2*pre[p], b = dp_pre[p] + pre[p]^2
        auto add = [&](int p){
            if(dp_pre[p] >= inf/2) return;   // 如果 dp_pre[p] 不可达，则不加入
            
            ll k = -2 * pre[p];
            ll b = dp_pre[p] + pre[p] * pre[p];
            // 直线方程：y = k * x + b
            
            // 处理相同斜率的情况：如果新直线与队尾直线斜率相同，保留截距更小的那条
            while(!q.empty()){
                int lst = q.back();
                ll lk = -2 * pre[lst];
                if(lk == k){
                    ll lb = dp_pre[lst] + pre[lst] * pre[lst];
                    if(lb <= b) return;   // 旧直线更优（截距更小），直接返回，不加入新直线
                    else q.pop_back();    // 否则弹出旧直线，继续检查
                }
                else break;
            }
            
            // 维护下凸壳：检查队尾两个点和当前点是否构成上凸，若是则弹出队尾
            while(q.size() >= 2){
                int l1 = q[q.size()-2];
                int l2 = q.back();
                int l3 = p;
                
                ll k1 = -2 * pre[l1], b1 = dp_pre[l1] + pre[l1] * pre[l1];
                ll k2 = -2 * pre[l2], b2 = dp_pre[l2] + pre[l2] * pre[l2];
                ll k3 = -2 * pre[l3], b3 = dp_pre[l3] + pre[l3] * pre[l3];
                
                // 判断 (l1, l2, l3) 是否构成下凸壳。若满足叉积条件，则弹出 l2
                if((b2 - b1) * (k2 - k3) >= (b3 - b2) * (k1 - k2)){
                    q.pop_back();
                }
                else break;
            }
            q.push_back(p);   // 将当前决策点加入凸壳
        };
        
        // 初始时，只有前 k-1 个元素可以作为分割点，即 j = k-1 是第一个合法决策点
        add(k-1);
        
        // 计算当前维 dp_cur[i]，i 从 k 到 n（至少需要 k 个元素才能分成 k 段）
        for(int i = k; i <= n; i++){
            // 查询：从队首弹出不优的直线，直到找到最优决策点
            while(q.size() >= 2){
                int l1 = q[0], l2 = q[1];
                ll k1 = -2 * pre[l1], b1 = dp_pre[l1] + pre[l1] * pre[l1];
                ll k2 = -2 * pre[l2], b2 = dp_pre[l2] + pre[l2] * pre[l2];
                ll x = pre[i];   // 查询点的横坐标
                
                // 如果 l1 在 x 处的值 >= l2 在 x 处的值，则 l1 不再是最优，弹出
                if(k1 * x + b1 >= k2 * x + b2) q.pop_front();
                else break;
            }
            
            int j = q.front();   // 最优决策点
            // 状态转移：dp_cur[i] = dp_pre[j] + (pre[i] - pre[j])^2
            dp_cur[i] = dp_pre[j] + (pre[i] - pre[j]) * (pre[i] - pre[j]);
            
            // 将当前点 i 作为新的决策点加入凸壳，供后续 i 使用
            add(i);
        }
        
        // 滚动数组：将当前维的结果复制到 dp_pre，供下一轮使用
        for(int i = 1; i <= n; i++){
            dp_pre[i] = dp_cur[i];
        }
    }
    
    // 最终答案：m * dp_pre[n] - (pre[n])^2
    // 这是因为 dp 中存储的是平方和，最终要转化为方差形式
    ll S = pre[n];
    ll ans = (ll)m * dp_pre[n] - S * S;
    cout << ans;
    return;
}

int main(){
    //freopen("in","r",stdin);
    //freopen("out","w",stdout);
    int T = 1;
    //cin >> T;
    while(T--){
        solve();
    }
    return 0;
}