[2016湖南长沙培训Day4][前鬼后鬼的守护 chen] (动态开点线段树+中位数 or 动规 or 贪心+堆优化)

时间：2021-01-11 20:52:59

题目大意

给定一个长度为n的正整数序列，令修改一个数的代价为修改前后两个数的绝对值之差，求用最小代价将序列转换为不减序列。

其中，n满足小于500000，序列中的正整数小于10^9

题解（引自mzx神犇的题解）

本次test跪0了，尴尬

解法1（40分）

考虑dp

设到第i个数为止，序列中数全部<=j的最小代价为f[i][j]

可以推出f[i][j]=min{f[i-1][j]+|ai-j|,f[i][j-1]}

解法2（60分）

是对于第一个dp思路的优化

既然数字是固定的，可以离散化，降低空间时间复杂度

解法3（100分）

斜率优化dp，用线段树维护斜率

解法4（100分，引自zyz大神的解法）

玄学的单调栈问题

由于区间中的数是单调不减的，所以最后得出的序列一定是一段一段的各个数值相等的序列区间

而要最小化代价，可以取这些区间中的中位数作为标准来修改每个区间，并用单调栈求解最优的区间划分

还需要用动态开点线段树维护区间中位数

orz

#include <stdio.h>

#include <string.h>

const int MAXN = 5e5 + ;

const int INF = 1e9 + ;

inline int abs(int x){

  return x <  ? -x : x;

}

int Rin(){

  int x = , c = getchar(), f = ;

  for(; c <  || c > ; c = getchar())

    if(!(c ^ ))

      f = -;

  for(; c >  && c < ; c = getchar())

    x = (x << ) + (x << ) + c - ;

  return x * f;

}

namespace Arcueid{

  struct Node{

    Node *l, *r;

    int s;

    Node(){}

    Node(Node *_l, Node *_r, int _s) : l(_l), r(_r), s(_s) {}

  }*_nil = new Node(), *nil = (*_nil = Node(_nil, _nil, ), _nil), pool[MAXN * ], *top = pool;

  Node *reborn(){

    *top = Node(nil, nil, );

    return top++;

  }

  void death(Node *&pr, Node *pl, int l, int r, int v){

    pr = reborn(); *pr = *pl; pr->s++;

    if(l +  < r){

      int mid = (l + r) >> ;

      v < mid ? death(pr->l, pl->l, l, mid, v) : death(pr->r, pl->r, mid, r, v);

    }

  }

  int secret(Node *pr, Node *pl, int l, int r, int k){

    if(l +  == r)return l;

    int c = pr->l->s - pl->l->s, mid = (l + r) >> ;

    return c < k ? secret(pr->r, pl->r, mid, r, k - c) : secret(pr->l, pl->l, l, mid, k);

  }

  int feel(Node *pr, Node *pl){

    int c = pr->s - pl->s;

    return secret(pr, pl, , INF, (c + ) >> );

  }

}

Arcueid::Node *rt[MAXN] = {Arcueid::nil};

namespace moon{

  void cause(){

    int n, a[MAXN], stay = , night[MAXN], shiki[MAXN];

    //    freopen("chen.in", "r", stdin);

    //    freopen("chen.out", "w", stdout);

    n = Rin();

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

      a[i] = Rin();

      Arcueid::death(rt[i], rt[i-], , INF, a[i]);

      for(; stay >  && Arcueid::feel(rt[i], rt[night[stay - ]]) < shiki[stay - ]; stay--);

      shiki[stay] = Arcueid::feel(rt[i], rt[night[stay-]]);

      night[stay++] = i;

    }

    long long ans = ;

    for(int i = ; i < stay; i++)

      for(int j = night[i - ] + ; j <= night[i]; j++)

    ans += abs(a[j] - shiki[i]);

    printf("%lld\n", ans);

    //    fclose(stdin);

    //    fclose(stdout);

  }

}

int main(){

  moon::cause();

  return ;

}

解法5（100分）

其实这个解法更玄

但最简洁的往往是最好的

#include <queue>

#include <vector>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

inline int read(){

  int x = , c = getchar(), f = ;

  for(; c <  || c > ; c=getchar())

    if(!(c ^ ))

      f = -;

  for(; c >  && c < ; c=getchar())

    x = (x << ) + (x << ) + c - ;

  return x * f;

}

long long ans = ;

priority_queue<int> q;

int main(){

  int n = read();

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

    int x = read();

    q.push(x);

    ans += q.top() - x;

    if(x ^ q.top())

      q.pop();

  }

  printf("%lld\n", ans);

  return ;

}

相关文章