DP单调性优化

orz hhw posted @ 2015年5月14日 13:17 in 算法学习 with tags DP 模板 bzoj 单调性 算法学习 , 727 阅读

单调性似乎一直没有解决,水平一直停留在只会单调求最长上升子序列的阶段。。。。

今天在网上看看资料,感觉单调性什么的也不用管,关键是网上找不到模板啊、、、

于是选一道单调队列的题,看AC的程序,整合出了一个单调性DP模板

[BZOJ1563][NOI2009]诗人小G:dp[i]=dp[j]+|sum[i]-sum[j]+i-j-1-L|^P,然后发现这是单调的、、

#include<cstdio>
#include<cstring>
#include<iostream>
#define N 123333
#define MAXANS 1e18
using namespace std;
typedef long double LD;typedef long long LL;
struct NODE{int l,r,id;}q[N];//当前DP的决策区间是[l,r],这部分区间是用f[id]更新的
int n,i,L,P,T,len[N];LD dp[N],sum[N];
char s[33];
LD pow(LD x){
	if(x<0)x=-x;LD ans=1;
	for(int i=1;i<=P;i++)ans*=x;
	return ans;
}
LD calc(int x,int y){return dp[y]+pow(sum[x]-sum[y]-L+x-y-1);}
void solve(){
	int head=0,tail=0;q[0]={1,n,0};
    for(int i=1;i<=n;i++){//DP到第i位,求出第i位的dp值
        while(i>q[head].r)head++;//让第i位包含在队首的决策区间里
        dp[i]=calc(i,q[head].id);//用队首被更新的dp[id]去更新dp[i]
        if(calc(n,i)>calc(n,q[tail].id))continue;//如果用队尾的被拿来更新的dp[id]去更新dp[n]比用dp[i]更新dp[n]好,就跳过后面更新决策区间的过程
        while(i<q[tail].l&&calc(q[tail].l,i)<calc(q[tail].l,q[tail].id))tail--;
        int l=max(q[tail].l,i+1);//i能拿来更新[i+1,n]的决策,那么我们要找出二分转折点的下界,就是最新的决策区间左端点与i+1的最大值
        int r=q[tail].r;//上界是最新的决策区间的右端点
        int ans=min(n,q[tail].r+1); //ans是二分出的转折点的位置
        while(l<=r){
            int mid=(l+r)>>1;
            if(calc(mid,i)<calc(mid,q[tail].id)){
                r=mid-1;
                ans=mid;
            }
            else l=mid+1;
        }
        q[tail].r=ans-1;//更新原来的决策区间的右端点
        q[++tail]={ans,n,i};//加入第i位的决策区间
    }
    if(dp[n]>MAXANS)puts("Too hard to arrange");
    else printf("%lld\n",(LL)dp[n]);
    puts("--------------------");
}
int main(){
	scanf("%d",&T);
	while(T--){
		sum[0]=0;
		scanf("%d%d%d",&n,&L,&P);
		for(i=1;i<=n;i++)scanf("%s",s),len[i]=strlen(s),sum[i]=sum[i-1]+len[i];
		solve();
	}
}

貌似没有其他单调性的题目了、、似乎其他题目就算用单调性斜率优化也能解决、、

#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 500500
using namespace std;
double f[N],g[N];
int n,i,l,r,mid,a[N];
struct data{int p,l,r;}q[N];
double cal(int j,int i){return a[j]+sqrt(abs(i-j))-a[i];}
void dp(double *f){
	for(int h=1,t=0,i=1;i<=n;i++){
		q[h].l++;if(h<=t&&q[h].l>q[h].r)h++;
		if(h>t||cal(i,n)>cal(q[t].p,n)){
			for(;h<=t&&cal(i,q[t].l)>cal(q[t].p,q[t].l);t--);
			if(h>t)q[++t]=(data){i,i,n};else{
				l=q[t].l;r=q[t].r;
				while(l<r){
					mid=l+r>>1;
					if(cal(q[t].p,mid)>cal(i,mid))l=mid+1;else r=mid;
				}
				q[t].r=l-1;q[++t]=(data){i,l,n};
			}
		}
		f[i]=cal(q[h].p,i);
	}
}
int main(){
	scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a[i]);
	dp(f);reverse(a+1,a+n+1);dp(g);
	for(i=1;i<=n;i++)printf("%d\n",(int)ceil(max(f[i],g[n-i+1])));
}

 

看了篇论文,讲到这道题,就是单调队列弄一下就行啦

#include<cstdio>
#include<iostream>
#define N 222
#define inf 1e8
using namespace std;
int n,m,x,y,k,i,j,now,s,t,fx,head,tail,ans,dp[N][N][N],q[N];
char map[N][N];
void up(int l){
	for(j=1;j<=m;j++){
		head=0;tail=-1;
		for(i=n;i;i--){
			dp[now][i][j]=dp[now^1][i][j];
			if(map[i][j]=='x'){head=0;tail=-1;continue;}
			if(dp[now^1][i][j]>=0){
				while(head<=tail&&dp[now^1][q[tail]][j]+q[tail]<=dp[now^1][i][j]+i)tail--;
				q[++tail]=i;
			}
			while(head<=tail&&q[head]-i>l)head++;
			if(head<=tail)dp[now][i][j]=max(dp[now][i][j],dp[now^1][q[head]][j]+q[head]-i);
		}
	}
}
void down(int l){
	for(j=1;j<=m;j++){
		head=0;tail=-1;
		for(i=1;i<=n;i++){
			dp[now][i][j]=dp[now^1][i][j];
			if(map[i][j]=='x'){head=0;tail=-1;continue;}
			if(dp[now^1][i][j]>=0){
				while(head<=tail&&dp[now^1][q[tail]][j]-q[tail]<=dp[now^1][i][j]-i)tail--;
				q[++tail]=i;
			}
			while(head<=tail&&i-q[head]>l)head++;
			if(head<=tail)dp[now][i][j]=max(dp[now][i][j],dp[now^1][q[head]][j]+i-q[head]);
		}
	}
}
void left(int l){
	for(i=1;i<=n;i++){
		head=0;tail=-1;
		for(j=m;j;j--){
			dp[now][i][j]=dp[now^1][i][j];
			if(map[i][j]=='x'){head=0;tail=-1;continue;}
			if(dp[now^1][i][j]>=0){
				while(head<=tail&&dp[now^1][i][q[tail]]+q[tail]<=dp[now^1][i][j]+j)tail--;
				q[++tail]=j;
			}
			while(head<=tail&&q[head]-j>l)head++;
			if(head<=tail)dp[now][i][j]=max(dp[now][i][j],dp[now^1][i][q[head]]+q[head]-j);
		}
	}
}
void right(int l){
	for(i=1;i<=n;i++){
		head=0;tail=-1;
		for(j=1;j<=m;j++){
			dp[now][i][j]=dp[now^1][i][j];
			if(map[i][j]=='x'){head=0;tail=-1;continue;}
			if(dp[now^1][i][j]>=0){
				while(head<=tail&&dp[now^1][i][q[tail]]-q[tail]<=dp[now^1][i][j]-j)tail--;
				q[++tail]=j;
			}
			while(head<=tail&&j-q[head]>l)head++;
			if(head<=tail)dp[now][i][j]=max(dp[now][i][j],dp[now^1][i][q[head]]+j-q[head]);
		}
	}
}
int main(){
	scanf("%d%d%d%d%d",&n,&m,&x,&y,&k);
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			char ch=getchar();
			while(ch!='x'&&ch!='.')ch=getchar();
			map[i][j]=ch;
			dp[0][i][j]=-inf;
		}
	}
	dp[0][x][y]=0;
	while(k--){
		now=1-now;
		scanf("%d%d%d",&s,&t,&fx);s=t-s+1;
		if(fx==1)up(s);
		else if(fx==2)down(s);
		else if(fx==3)left(s);
		else if(fx==4)right(s);
	}
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if(dp[now][i][j]>ans)ans=dp[now][i][j];
	printf("%d",ans);
}

登录 *


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