「JZOJ3859」孤独一生 - 动态规划+树状数组

题目大意

    下课了，Polo来到球场，但他到了之后才发现…被放了飞机…
    无事可做的他决心找点乐子，比方说……跳台阶……
    球场边有N个台阶拍成一行，第$i$个台阶的高度是$H_i(0\lt H_i\le10^9)$，第$0$个台阶，也就是地面的高度为$0$。Polo打算把这$N$个台阶分成两个集合$S_a,S_b$（可以为空），对于一个台阶集合$S=\lbrace P_1,P_2,…P_{|S|}\rbrace$，其中$P_1\lt P_2\lt\ldots\lt P_{|S|}$，他需要花费$\sum_{i=1}^{|S|}|H_{p_i}-H_{p_{i-1}}|$的体力值来完成。
    现在他希望两次跳跃所需的总体力值最小，你能帮帮他吗？

---

题目分析

我们可以分别设状态将两个集合的末尾位置表示出来并互相转移。
但是写出的状态转移方程竟然一模一样！

仔细分析也可发现，其实分的是哪个集合对本题并无影响，真正带来影响的是集合的分割点。

设$f[i]$表示在$i$之前进行分割，将$i$以后的分割出来的最小代价。

因此：

$$f[i]=\min_{j=1}^{i-1}\begin{cases}f[j]+sum[i-1]-sum[j]+\mid a_i-a_{j-1}\mid\end{cases}$$

其中，$sum[]$是差绝对值的前缀和。

然后就可以写出$50$分的暴力了。

$100$分我们可以采用树状数组优化动态规划方程。
将绝对值拆开，用树状数组分别维护$f[i]-sum[i]-a[i-1]$与$f[i]-sum[i]+a[i-1]$即可。

树状数组的维护方式是：维护两个树状数组，一个表示比$a[i]$更小$a[j-1]$的$f[j]-sum[j]-a[j-1]$的值，另一个反之。

因此我们可以用$a[]$作下标建立树状数组，需要事先离散化。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;

inline const LL Get_Int() {
	LL num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=500005;
int n;
LL a[maxn],sum[maxn],f[maxn],tmp[maxn],b[maxn];

struct BIT1 {
	LL c[maxn];
#define lowbit(x) x&-x
	BIT1() {
		memset(c,0x7f,sizeof(f));
	}
	void add(int x,LL v) {
		for(int i=x; i<=n+1; i+=lowbit(i))c[i]=min(c[i],v);
	}
	LL ask(int x) {
		LL ans=LLONG_MAX/2;
		for(int i=x; i>=1; i-=lowbit(i))ans=min(ans,c[i]);
		return ans;
	}
} bit1;

struct BIT2 {
	LL c[maxn];
#define lowbit(x) x&-x
	BIT2() {
		memset(c,0x7f,sizeof(f));
	}
	void add(int x,LL v) {
		for(int i=x; i>=1; i-=lowbit(i))c[i]=min(c[i],v);
	}
	LL ask(int x) {
		LL ans=LLONG_MAX/2;
		for(int i=x; i<=n+1; i+=lowbit(i))ans=min(ans,c[i]);
		return ans;
	}
} bit2;

void Discretization(LL* a) {
	memcpy(b,a,sizeof(b));
	sort(a+1,a+n+1);
	int cnt=unique(a+1,a+n+1)-a-1;
	for(int i=1; i<=n; i++)b[i]=lower_bound(a+1,a+cnt+1,b[i])-a+1;
}

int main() {
	n=Get_Int();
	for(int i=1; i<=n; i++) {
		a[i]=Get_Int();
		tmp[i]=a[i];
		sum[i]=sum[i-1]+abs(a[i]-a[i-1]);
	}
	Discretization(tmp);
	b[0]=1;
	for(int i=1; i<=n; i++) {
		if(i==1)f[1]=a[1];
		else f[i]=min(bit1.ask(b[i])+sum[i-1]+a[i],bit2.ask(b[i])+sum[i-1]-a[i]);
		bit1.add(b[i-1],f[i]-sum[i]-a[i-1]);
		bit2.add(b[i-1],f[i]-sum[i]+a[i-1]);
	}
	for(int i=1; i<=n; i++)f[n]=min(f[n],f[i]+sum[n]-sum[i]);
	printf("%lld\n",f[n]);
	return 0;
}