SDOI2016 征途

题目:

  Pine开始了从S地到T地的征途。
  从S地到T地的路可以划分成 段,相邻两段路的分界点设有休息站。
  Pine计划用 天到达T地。除第 天外,每一天晚上Pine都必须在休息站过夜。所以,一段路必须在同一天中走完。
  Pine希望每一天走的路长度尽可能相近,所以他希望每一天走的路的长度的方差尽可能小。
  帮助Pine求出最小方差是多少。
  设方差是v,可以证明, 是一个整数。为了避免精度误差,输出结果时输出

思路:

  第一次看到这题的时候直接用分治和决策单调 过了,结果听说可以 二分可以做到 就滚去学了一下(所以主要是一篇学习笔记?)
  先是可以推导一下发现题目要求的就是 是每一段的长度)。因为 都是常量,所以要求的就是
  如果按照常规的思路,因为题目中限制了划分的段数,所以一般都是用 来表示状态的。这样状态数就达到了
  注意到当 增大时,答案一定是不增的,所以可以考虑利用这个单调性。考虑再加入一个权重 ,每划出一段就再加上一个代价 。当 变大时,划分的段数就会减小,这样就能二分是得划分的段数等于 了,而没有段数限制的 可以用斜率优化做到 ,所以就能做到 了。
  但是有可能不存在一个 使得划分段数等于 ,而论文中的原话是:(这是我不太理解的地方,就留个坑在这吧)

  如果发现 时,所有最优解中最小的分段数大于 ,而取 时最小的分段数小于 ,那么 时也存在分段数为 的最优解,只需取此时的最优答案减

代码:

#include <bits/stdc++.h>
#define P2(x) ((ll) (x) * (x)) 
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--) 
using namespace std; 
const int N = 3005;
typedef long long ll;
typedef double db;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}

int a[N], g[N], n, m;
ll dp[N], s[N];
struct Point {
    ll x, y;
    int id;
};
Point p[N];
bool check(Point a, Point b, Point c) {
    return (db) (a.y - b.y) * (b.x - c.x) >= (db) (b.y - c.y) * (a.x - b.x);
}
ll getDp(int i, int o, ll c) {
    return dp[o] + P2(s[i] - s[o]) + c;
}
void calc(ll c) {
    int hed = 1, tai = 0;
    p[++tai] = (Point) {0, 0, 0};
    rep(i, 1, n) {
        while(hed < tai && getDp(i, p[hed].id, c) > getDp(i, p[hed + 1].id, c)) hed++;
        int o = p[hed].id;
        g[i] = g[o] + 1;
        dp[i] = getDp(i, o, c);
        Point t = (Point) {s[i], dp[i] + P2(s[i]), i};
        while(hed < tai && check(p[tai - 1], p[tai], t)) tai--;
        p[++tai] = t;
    }
}

int main() {
    // freopen("data.in", "r", stdin);
    scanf("%d%d", &n, &m);
    rep(i, 1, n) {
        scanf("%d", a + i);
        s[i] = a[i] + s[i - 1];
    }
    ll L = 0, R = P2(s[n]);
    ll ans = 0;
    while(L <= R) {
        ll mid = (L + R) >> 1;
        calc(mid);
        if(g[n] <= m) {
            ans = dp[n] - m * mid;
            R = mid - 1;
        }
        else L = mid + 1;
    }
    printf("%lld\n", ans * m - P2(s[n]));
    return 0;
}