DP单调性优化
单调性似乎一直没有解决，水平一直停留在只会单调求最长上升子序列的阶段。。。。
今天在网上看看资料，感觉单调性什么的也不用管，关键是网上找不到模板啊、、、
于是选一道单调队列的题，看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);
}
评论 (0)
