又做了一道适合我这种沙茶做的题qwq

考虑方差，它满足这个式子：

\[Var(X) = E[X^2] - (E[X])^2\]

对于这个题展开，发现后半部分是一个常量（\((\frac{s_n}{m})^2\)）。最小化的就是前半部分，前半部分相当于要求你求一个序列划分，使得各部分平方和的平均值最小。这个值乘上\(m^2\)之后就变成了各部分平方和乘上\(m\)。

然后就很简单了……DP方程化简之后是这样的：

\[f_{t, i} = ms_i^2 + max(f_{t - 1, j} + ms_j^2 - 2ms_i s_j)\]

求截距式形式，得：

\[2ms_i s_j + d_i = f_j + ms_j^2\]

然后用类似于上上题的方法搞就行。还有我想想啥时候补一下斜率优化的tutorial……

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <deque>
#include <cmath>
#include <climits>
typedef long long ll;
typedef ll T;
struct Point {
  T x, y;
  Point(T qx = 0LL, T qy = 0LL) {
    x = qx; y = qy;
  }
};
typedef Point Vector;
Vector operator +(const Vector &a, const Vector &b) {
  return Vector(a.x + b.x, a.y + b.y);
}
Vector operator -(const Point &a, const Point &b) {
  return Vector(a.x - b.x, a.y - b.y);
}
Vector operator *(const Vector &a, T lam) {
  return Vector(a.x * lam, a.y * lam);
}
Vector operator *(T lam, const Vector &a) {
  return Vector(a.x * lam, a.y * lam);
}
inline T dot(const Vector &a, const Vector &b) {
  return (a.x * b.x + a.y * b.y);
}
inline T times(const Vector &a, const Vector &b) {
  return (a.x * b.y - a.y * b.x);
}
 
const int maxn = 3005;
T f[maxn][maxn];
T S[maxn];
int n; T m;
void dp() {
  for(int t = 1; t <= m; t ++) {
    std::deque<Point> Q;
    Q.push_back(Point(0LL, 0LL));
    for(int i = 1; i <= n; i ++) {
      ll k = 2 * m * S[i];
      Vector st(1LL, k);
      while(Q.size() > 1 && times(Q[1] - Q[0], st) > 0LL) {
        Q.pop_front();
      }
      f[t][i] = m * S[i] * S[i];
      f[t][i] += Q.front().y - Q.front().x * k;
#ifdef LOCAL
      printf("f[%d][%d] : %lld\n", t, i, f[t][i]);
#endif
      if(t == 1) continue;
      Vector ins(S[i], f[t - 1][i] + m * S[i] * S[i]);
      while(Q.size() > 1 && times(ins - Q.back(), Q.back() - Q[Q.size() - 2]) > 0LL) {
        Q.pop_back();
      }
      Q.push_back(ins);
    }
  }
}

int main() {
  scanf("%d%lld", &n, &m);
  for(int i = 1; i <= n; i ++) {
    scanf("%lld", &S[i]);
  }
  for(int i = 1; i <= n; i ++) {
    S[i] += S[i - 1];
  }
  dp();
  printf("%lld\n", f[m][n] - S[n] * S[n]);
  return 0;
}

• 相关文章
• 全局相关文章