树状数组优化DP 【模拟赛】删区间

时间：2023-03-09 20:23:06
树状数组优化DP 【模拟赛】删区间

树状数组优化DP 【模拟赛】删区间

哇,难受得一匹.

看到题的一瞬间竟然只想到了\(n^3\)的区间\(DP\)

一.\(40pts\)

设\(f[i][j]\)代表删去\(i\)到\(j\)这一段区间的最小代价和.

然后直接写普通的区间\(DP\)即可.

for(int i=n-1;i>=1;i--)

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

    {

        f[i][j]=abs(a[j]-a[i]);

        for(int k=i+1;k<j-1;k++)

            f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);

	}
二.\(70pts\)

设\(f[i]\)代表删去\(1\)到\(i\)这一段的最小代价和.

两分钟写的比考试的时候写到的要得分高qwq

然后\(n^2\)枚举即可.

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

	for(int j=1;j<i;j++)

		f[i]=min(f[i],f[j-1]+abs(a[j]-a[i]));
三.\(100pts\)

考虑优化,我们的状态转移的第二项会有两种情况.

这里设\(A=a[i]\)，\(B=a[j]\)。

\(abs\)会出现两种情况

\[f[i]=f[j-1]+A-B\ (A\leq B)\\f[i]=f[j-1]+B-A\ ( B<A)
\]

此时\(A\)已知,因此维护两个东西.

  1. \(f[j-1]+B\)
  2. \(f[j-1]-B\)

用什么维护?发现这个东西是前缀,所以考虑树状数组

维护的东西就是上面的,然后每次询问之后,再加入\(f[i-1]+A\)与\(f[i-1]-B\)

PS：这里要开两个树状数组,具体看代码。

注意其中一个树状数组要反转.

代码

#include<cstdio>

#include<cctype>

#include<cmath>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<iostream>

#define N 500008

#define R register

#define clear(a,b) memset(a,b,sizeof a)

#define int long long

using namespace std;

inline void in(int &x)

{

	int f=1;x=0;char s=getchar();

	while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}

	while(isdigit(s)){x=x*10+s-'0';s=getchar();}

	x*=f;

}

int f[N],a[N],n,b[N];

#define lowbit(o) o&-o

int aa[N],bb[N];

inline void adda(int o,int x)

{

	for(;o<=n;o+=lowbit(o))

		aa[o]=min(aa[o],x);

}

inline void addb(int o,int x)e

{

	o=n-o+1;

	for(;o<=n;o+=lowbit(o))

		bb[o]=min(bb[o],x);

}

inline int querya(int o)

{

	R int res=214748364000LL;

	for(;o;o-=lowbit(o))

		res=min(res,aa[o]);

	return res;

}

inline int queryb(int o)

{

	R int res=214748364000LL;

	o=n-o+1;

	for(;o;o-=lowbit(o))

		res=min(res,bb[o]);

	return res;

}

signed main()

{

	freopen("remove.in","r",stdin);

	freopen("remove.out","w",stdout);

	in(n);

	for(R int i=1;i<=n;i++)in(a[i]),b[i]=a[i];

	sort(b+1,b+n+1);

	for(R int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+n+1,a[i])-b;

	clear(f,0x3f);f[0]=0;

	clear(bb,0x3f),clear(aa,0x3f);

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

	{

		int tma=querya(a[i]),tmb=queryb(a[i]);

		f[i]=min(f[i],b[a[i]]+tma);

		f[i]=min(f[i],-b[a[i]]+tmb);

		adda(a[i],f[i-1]-b[a[i]]);

		addb(a[i],f[i-1]+b[a[i]]);

	}

	printf("%lld",f[n]);

}

相关文章