bzoj3675: [Apio2014]序列分割

留坑

为什么别人家的斜率优化跟我一点都不一样！

为什么斜率都要变成正的。。。

为什么要那么推式子

为什么不能直接做啊。。。。。

为什么不把0去掉去秒WA啊

为什么叉积去了0也过不了啊

woc啊

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<algorithm>

 #include<iostream>

 using namespace std;

 void setIO(const string& s) {

     freopen((s + ".in").c_str(), "r", stdin);

     freopen((s + ".out").c_str(), "w", stdout);

 }

 template<typename Q> Q read(Q& x) {

     static char c, f;

     for(f = ; c = getchar(), !isdigit(c); ) if(c == '-') f = ;

     for(x = ; isdigit(c); c = getchar()) x = x *  + c - '';

     if(f) x = -x;

     return x;

 }

 template<typename Q> Q read() {

     static Q x; read(x); return x;

 }

 typedef long long LL;

 const int N =  + ;

 LL sqr(const LL& x) {

     return x * x;

 }

 LL f[N], g[N], sum[N];

 int q[N];

 LL up(int i) {

     return g[i] - sqr(sum[i]);

 }

 LL up(int i, int j) {

     return up(j) - up(i);

 }

 LL down(int i, int j) { // >= 0

     return sum[j] - sum[i];

 }

 double slope(int i, int j) {

     return up(i, j) / (double) down(i, j);

 }

 int n;

 struct Node {

     LL x, y;

     Node() {}

     Node(const LL& x, const LL& y) : x(x), y(y) {}

     Node operator - (const Node& rhs) const {

         return Node(x - rhs.x, y - rhs.y);

     }

 }p[N];

 LL Cross(const Node& a, const Node& b) {

     return a.x * b.y - b.x * a.y;

 }

 void dp(int st) {

     int L = , R = ;

     q[R++] = st;

     for(int i = st + ; i <= n; i++) {

 //        while(L + 1 < R && -sum[i] < slope(q[L], q[L + 1])) L++;

 //        while(L + 1 < R && -sum[i] * down(q[L], q[L + 1]) < up(q[L], q[L + 1])) L++;

         while(L +  < R && Cross(Node(, -sum[i]), p[L + ] - p[L]) >= ) L++;

         int j = q[L];

         f[i] = g[j] + sum[j] * (sum[i] - sum[j]);

 //        while(L + 1 < R && slope(q[R - 2], q[R - 1]) < slope(q[R - 2], i)) R--;

 //        while(L + 1 < R && up(q[R - 2], q[R - 1]) * down(q[R - 2], i) < up(q[R - 2], i) * down(q[R - 2], q[R - 1])) R--;

         Node u(sum[i], up(i));

         while(L +  < R && Cross(p[R - ] - p[R - ], u - p[R - ]) >= ) R--;

         q[R] = i, p[R++] = u;

     }

     for(int i = st + ; i <= n; i++) g[i] = f[i];

 }

 int main() {

 #ifdef DEBUG

     freopen("in.txt", "r", stdin);

     freopen("out.txt", "w", stdout);

 #endif

     read(n);

     int k = read<int>();

     for(int i = ; i <= n; i++) {

         int x = read<int>();

         if(!x) i--, n--;

         else sum[i] = sum[i-] + x;

 //        sum[i] = sum[i-1] + read<int>();

     }

     for(int i = ; i <= k; i++) dp(i);

     printf("%lld\n", g[n]);

     return ;

 }