CF1175G

叉姐牛逼。

\(f_{k,i} = \min_{0\leq j <i}{f_{k - 1,j} + RMQ(j + 1,i) * (i - j)}\)

我们考虑在序列上分治一波。

按照\(m\)切开，\(i >= m\),

我们需要找到

\(\min_{0\leq j < m} f_{k - 1,j} + \max{(suf[j],pre[i])} * (i - j)\)

然后我们发现此时\(suf[j]\)具有单调性。

我们可以分类讨论一下。

\(suf_j \leq pre_i\)

我们需要找到

\(\min_j g_j - pre[i] * j\)

否则

我们需要找到

\(min_j(g_j - suf_j * j) + i _suf[j]\)

考虑分治加单调栈处理。

叉姐牛逼。

#include<iostream>

#include<cstdio>

#include<algorithm>

#define N 20001

#define INF 400000005

struct Line{

	int k,b;

	int val(int x){return k * x + b;}

};

inline bool check(Line u,Line v,Line w){

	return 1ll * (v.b - u.b) * (v.k - w.k) < 1ll * (w.b - v.b) * (u.k - v.k);

}

inline void qmin(int &x,int a){x = (x > a) ? a : x;}

int n,a[N],dp[2][N],suf[N],pre[N];

Line stack[N];

#define m ((l + r) >> 1)

inline void work(int *pdp,int *dp,int l,int r){

	if(l < r){

    suf[m] = 0;

    for (int i = m; i > l; --i) {

      suf[i - 1] = std::max(a[i], suf[i]);

    }

    pre[m] = 0;

    for (int i = m + 1; i <= r; ++i) {

      pre[i] = std::max(pre[i - 1], a[i]);

    }

    for (int i = m + 1, bot = n, j = m; i <= r; ++i) {

      while (j >= l && suf[j] <= pre[i]) {

        const Line line{-j, pdp[j]};

        while (bot + 1 < n && !check(line, stack[bot], stack[bot + 1])) {

          bot++;

        }

        stack[--bot] = line;

        j--;

      }

      int x = pre[i];

      while (bot + 1 < n && stack[bot].val(x) > stack[bot + 1].val(x)) {

        bot++;

      }

      qmin(dp[i], stack[bot].val(x) + i * pre[i]);

    }

    for (int i = r, top = -1, j = l; i > m; --i) {

      while (j <= m && suf[j] >= pre[i]) {

        Line line{suf[j], pdp[j] - j * suf[j]};

        j++;

        while (j <= m && suf[j] == line.k) {

          line.b = std::min(line.b, pdp[j] - j * suf[j]);

          j++;

        }

        while (top - 1 >= 0 && !check(stack[top - 1], stack[top], line)) {

          top--;

        }

        stack[++top] = line;

      }

      int x = i;

      while (top - 1 >= 0 && stack[top - 1].val(x) < stack[top].val(x)) {

        top--;

      }

      if (~top) {

        qmin(dp[i], stack[top].val(x));

      }

    }

    work(pdp, dp, l, m);

    work(pdp, dp, m + 1, r);

	}

}

int main() {

  int M;

  scanf("%d%d", &n, &M);

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

    scanf("%d", a + i);

  }

  dp[0][0] = 0;

  std::fill(dp[0] + 1, dp[0] + n + 1, INF);

  for (int j = 0; j < M; ++j) {

    std::fill(dp[(j + 1) & 1], dp[(j + 1) & 1] + (n + 1), INF);

    work(dp[j & 1], dp[(j + 1) & 1], 0, n);

  }

  printf("%d\n", dp[M & 1][n]);

}

巴特西

CF1175G

最新文章

热门文章