又做了一个简单的斜率优化题TAT

首先，设\(f_i\)表示最后一个放塔的点事\(i\)时的最优解，那么将原方程化简得：

\[f_i = a_i + \frac{i^2 - i}{2} + max(-ij + \frac{j^2 + j}{2} + f_j)\]

然后求直线形式，得到：

\[ij + d_i = f_j + \frac{j^2 + j}{2}\]

用类似于玩具装箱（上一篇题解）的方式搞一搞即可。

代码：

/**************************************************************
	Problem: 3156
	User: danihao123
	Language: C++
	Result: Accepted
	Time:2496 ms
	Memory:16480 kb
****************************************************************/

#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 = 1000005;
T f[maxn], a[maxn];
int n;
void dp() {
  f[1] = a[1];
  std::deque<Point> Q;
  Q.push_back(Point(1LL, f[1] + 1LL));
  for(T i = 2; i <= n; i ++) {
    T k = i;
    Vector st(1LL, k);
    while(Q.size() > 1 && times(Q[1] - Q[0], st) > 0LL) {
      Q.pop_front();
    }
    f[i] = a[i] + ((i * i - i) / 2LL);
    f[i] += Q.front().y - Q.front().x * i;
    Point ins(i, f[i] + ((i * i + i) / 2LL));
    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", &n);
  for(int i = n; i >= 1; i --) {
    scanf("%lld", &a[i]);
  }
  dp();
  ll ans = f[n];
#ifdef LOCAL
  printf("f[n] : %lld\n", ans);
#endif
  for(T i = 1; i < n; i ++) {
#ifdef LOCAL
    printf("f[%d] : %lld\n", i, f[i]);
#endif
    ans = std::min(ans, f[i] + (n - i + 1LL) * (n - i) / 2LL);
  }
  printf("%lld\n", ans);
  return 0;
}

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