APIO2014 序列分割

题目:

  你正在玩一个关于长度为 的非负整数序列的游戏。这个游戏中你需要把序列分成 个非空的块。为了得到 块,你需要重复下面的操作 次:
  1.选择一个有超过一个元素的块(初始时你只有一块,即整个序列)
  2.选择两个相邻元素把这个块从中间分开,得到两个非空的块。
  每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。

思路:

  如果把 分开,贡献就是
  所以如果划分成三个区间,也就是三个区间两两互乘,所以可以得出决策的先后不影响答案。
  那么就能得到 ,展开之后发现可以斜率优化,所以复杂度就能做到 了。

代码:

#include <bits/stdc++.h>
#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--)
#define File(_) freopen(#_ ".in", "r", stdin), freopen(#_ ".out", "w", stdout)
#define P2(x) ((ll) (x) * (x))
using namespace std;
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;}
typedef long long ll;
typedef long double ldb;
const int N = 100005;

template<class T>
inline void rd(T &a) {
#define gc getchar()
    char c;
    bool f = false;
    for(c = gc; !isdigit(c); c = gc) f |= (c == '-');
    for(a = 0; isdigit(c); c = gc) a = (a << 1) + (a << 3) + c - '0';
    if(f) a = -a;
#undef gc
}

bool cur1;

int a[N], s[N];

struct Point {
    int x;
    ll y;
    int id;
} que[N];
bool cmp(Point a, Point b, Point c) {
    return (ldb) (a.y - b.y) * (c.x - b.x) >= (ldb) (c.y - b.y) * (a.x - b.x);
}
bool cmp(Point a, Point b, int t) {
    return (b.y - a.y) > (ll) (b.x - a.x) * t;
}

ll dp[205][N];
int frm[205][N];
int ans[205];

bool cur2;

int main() {
    // printf("%lf\n", (&cur2 - &cur1) / 1024.0 / 1024);
    File(sequence);
    int n, k;
    rd(n); rd(k);
    rep(i, 1, n) {
        rd(a[i]);
        s[i] = a[i] + s[i - 1];
    }
    int hed, tai;
    rep(p, 1, k) {
        que[hed = tai = 1] = (Point) {s[p], dp[p - 1][p] - P2(s[p]), p};
        rep(i, p + 1, n) {
            while(hed != tai && cmp(que[hed], que[hed + 1], -s[i])) hed++;
            int id = que[hed].id;
            dp[p][i] = dp[p - 1][id] - P2(s[id]) + (ll) s[i] * s[id];
            frm[p][i] = id;
            Point tmp = (Point) {s[i], dp[p - 1][i] - P2(s[i]), i};
            while(hed != tai && cmp(que[tai - 1], que[tai], tmp)) tai--;
            que[++tai] = tmp;
        }
    }
    printf("%lld\n", dp[k][n]);
    int o = n;
    drep(p, k, 1) {
        o = frm[p][o];
        printf("%d%c", o, " \n"[p == 1]);
    }
    return 0;
}