CF101234E

cwy posted @ 2017年11月08日 20:37 in CF , 33 阅读

给你一个排列,删掉每个数代价是ci,删掉这个数的同时这个数前面比他大的和这个数后面比他小的也会同时消失,要求花最小代价删光所有数。

首先观察可知,删掉的数形成一个极长上升子序列。

这个就得到了一个简单的O(n^2) DP。

听说可以树套树优化?

考虑分治,用左边的DP值去更新右边的DP值。

首先因为是极大的,所以左边的有用状态肯定是呈现递减状物,而且可以发现每个状态到下一个有用的状态连边,形成了一棵树。

对右边的数在左边找状态去转移的时候,从左边低于他的最高的开始,一直往树上的父亲爬,直到太低了为止,用倍增优化即可,复杂度nlog^2n。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;++i)
#define FORD(i,a,b) for (int i=a;i>=b;--i)
using namespace std;
typedef pair<int,int> pa;
typedef long double ld;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
const int INF=1e9+10;
int n,p[200010],c[200010],dp[200010],f[200010][20],v[200010][20];
int que(int x,int t,int m){
	if (p[x]<=t) return INF;
	int ans=INF;
	FORD(i,19,0)
		if (f[x][i]!=m+1 && p[f[x][i]]>t) ans=min(ans,v[x][i]),x=f[x][i];
	ans=min(ans,v[x][0]);
	return ans;
}
void cdq(int l,int r){
	if (l==r) return;
	int m=l+r>>1;
	cdq(l,m);
	map<int,int> st;
	st[-2]=m+1;
	FOR(i,0,19) f[m+1][i]=m+1,v[m+1][i]=INF;
	FORD(i,m,l){
		int t=(--st.lower_bound(p[i]))->se;
		st[p[i]]=i;
		f[i][0]=t,v[i][0]=dp[i];
		FOR(j,1,19) f[i][j]=f[f[i][j-1]][j-1],v[i][j]=min(v[i][j-1],v[f[i][j-1]][j-1]);
	}
	set<int> ts;
	ts.insert(-2);
	FOR(i,m+1,r){
		int t=*(--ts.lower_bound(p[i]));
		dp[i]=min(dp[i],que((--st.lower_bound(p[i]))->se,t,m)+c[i]);
		ts.insert(p[i]);
	}
	cdq(m+1,r);
}
int main(){
	scanf("%d",&n);
	FOR(i,1,n) getint(p[i]);
	p[n+1]=n+1;
	FOR(i,1,n) getint(c[i]);
	dp[0]=0;
	FOR(i,1,n+1) dp[i]=INF;
	cdq(0,n+1);
	cout<<dp[n+1]<<endl;
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter