美文网首页动态规划
DP训练——单调队列优化DP

DP训练——单调队列优化DP

作者: 云中翻月 | 来源:发表于2020-02-27 12:40 被阅读0次

单调队列DP

HDU5945
题意
给定整数X,k,t(X,j,t<=1e6)，存在如下两种操作。
1.X=X−i(0<=i<=t)
2.如果 k|X，X=X/k
求让X变为1的最小操作次数。
题解
状态定义：f[i]表示将i变成1的最小次数
目标：f[X]
边界：f[1]=0，其他为INF
转移方程：f[i]=min(f[i/k](i\%k==0),f[i-j](1<=j<=t))+1
上面的方程时间复杂度为O(Xt)，于是考虑优化。
我们发现，对于外层i来说，内层的j的范围为[i-t+1,i-1]。
因为这个范围的左右端点都会随着i的增大而增大，而转移时需要的是这个范围内的最小值，所以可以考虑用一个单调递增的单调队列来维护[i-t+1,i-1]上的最小f值下标。
PS：
使用单调队列优化计算第i个状态时的步骤。
1 判断队首是否满足条件，不满足则不断弹出队首。
2 利用队首来更新状态i的答案。（如果是单调栈，则此时利用队尾来更新状态i的答案）
3 判断如果加入i后，队尾队首是否满足条件，不满足则不断弹出队尾。
4 从队尾插入i。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1e6+5;
const int INF=0x3f3f3f3f;
int T;
int X,k,t;
int f[maxn];
int q[maxn],head,tail;
void init(){
    memset(f,INF,sizeof(f));
    head=1,tail=0;
}
void dp(){
    f[1]=0;
    q[++tail]=1;
    for(int i=2;i<=X;i++){
        while(tail-head+1>t) head++;
        if(i%k==0) f[i]=min(f[i],f[i/k]+1);
        f[i]=min(f[i],f[q[head]]+1);
        while(head<=tail&&f[q[tail]]>f[i]) tail--;
        q[++tail]=i;
    }
    cout<<f[X]<<endl;
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("HDU5945.in","r",stdin);
    cin>>T;
    while(T--){
        cin>>X>>k>>t;
        init();
        dp();
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

BZOJ1293
题意
n(n<=1000000)个珠子，共有k(k<=60)种，给定每个珠子的坐标，求最短区间，使得该区间包含所有种类的珠子。
题解
这题放在单调队列优化DP一章里，我想了半天没有头绪。
结果最后发现可以直接贪心。
首先将珠子坐标升序排序后，用last[i]表示第i种珠子最后一次出现的位置。
则从左往右扫描时，一旦发现已经能包括所有珠子时，就用last数组来更新答案即可。
唯一的坑点在于，最后答案可能很大，所以最大值不用能0x3f3f3f3f，最少为0x7fffffff。
时间复杂度O(nk)。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1000000+5;
const int maxk=60+5;
const ll INF=0x3f3f3f3f3f3f3f3fll;
int n,k;
struct node{
    int type;
    ll x;
    // node(int _type,ll _x){
    //     type=_type,x=_x;
    // }
    bool operator<(const node& h)const{return x<h.x;}
}p[maxn];
ll last[maxk]; //last[i]表示第i种珠子最后一次出现的位置
ll ans=INF;
void solve(){
    sort(p+1,p+n+1);
    /*
    for(int i=1;i<=n;i++){
        D(p[i].type);D(p[i].x);E;
    }
    */
    for(int i=1;i<=n;i++){
        last[p[i].type]=p[i].x;
        int cnt=0;
        ll minx=INF;
        for(int j=1;j<=k;j++){
            if(last[j]){
                cnt++;
                minx=min(minx,last[j]);
            }
        }
        if(cnt==k){
//            D(p[i].x);D(minx);E;
            ans=min(ans,p[i].x-minx);
        }
    }
    printf("%lld",ans);
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("BZOJ1293.in","r",stdin);
    scanf("%d%d",&n,&k);
    int tot=0;
    for(int i=1;i<=k;i++){
        int num;
        scanf("%d",&num);
        for(int j=1;j<=num;j++){
            ll x;
            scanf("%lld",&x);
            p[++tot].type=i;
            p[tot].x=x;
        }
    }
    solve();
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

BZOJ1499
题意
n行m列(n,m<=200)的矩阵中，有些点不可通行。
有一台钢琴初始位于(x,y)，每个时刻，它可以选择，是否根据矩阵的倾斜方向，向着上下左右四个方向移动。
已知全程的矩阵倾斜状态（倾斜状态用k(k<=200)个区间表示），求钢琴移动距离的最大值。
题解
状态定义：d[t,i,j]表示到第t个时间段，钢琴位于(i,j)的最长移动距离
目标：max(d[k,,])
边界：d[0,x,y]=0，其他为-INF
转移方程：d[t,i,j]=max(d[t-1,i*,j*]+dis(i*,j*,i,j))(i*,j*)为上一个合理的位置。
时间复杂度O(k*n^3)，空间复杂度O(k*n^2)，都需要优化。
注意到d[t,,]仅仅依赖于d[t-1,,]，因此可以压缩掉第一维，解决了空间限制。
注意到dis(i*,j*,i,j)=|i-i*|或|j-j*|，因此可以每次只考虑当前区间所在的行/列，化二维为一维，用单调队列来维护区间最值。
题解链接 https://www.luogu.com.cn/problemnew/solution/P2254
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=200+5;
const int maxk=200+5;
const int INF=0x3f3f3f3f;
const int dx[]={0,-1,1,0,0};
const int dy[]={0,0,0,-1,1};
int n,m,k;
char a[maxn][maxn];
struct node{
    int d,pos;
};
node q[maxn];
int head,tail;
int ans=-INF;
int d[maxn][maxn];
void init(){
    head=1,tail=0;
}
bool check(int x,int y){
    if(x<1||x>n||y<1||y>m) return false;
    return true;
}
void dp(int x,int y,int len,int dir){
    init();
    int cnt=0;
    while(1){
        cnt++;
        if(!check(x,y)) break;
        if(a[x][y]=='x'){
            init();
        }
        else{
            while(head<=tail&&q[tail].d+cnt-q[tail].pos<d[x][y]) tail--; //队首存储最大值，因此为单调递减队列。
            //这里之所以是q[tail].d+cnt-q[tail].pos，而不是q[tail].d。是因为需要纪录额外偏移量。
            q[++tail] = (node){d[x][y], cnt}; //存储上一个时间段的状态d[t-1,,]
            while(q[tail].pos-q[head].pos>len) head++;
            d[x][y]=q[head].d+cnt-q[head].pos;//更新这一个时间段的状态d[t,,] dis(i*,j*,i,j)=cnt-q[head].pos
            ans=max(ans,d[x][y]);
        }
        x+=dx[dir],y+=dy[dir];
    }
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("BZOJ1499.in","r",stdin);
    int sx,sy;
    scanf("%d%d%d%d%d",&n,&m,&sx,&sy,&k);
    memset(d,0xf3,sizeof(d));
    d[sx][sy]=0;
    for(int i=1;i<=n;i++){
        getchar();
        for(int j=1;j<=m;j++) scanf("%c",&a[i][j]);
    }
    /*
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) printf("%c",a[i][j]);
        printf("\n");
    }
    */
    int s,t,dir;
    while(k--){
        scanf("%d%d%d",&s,&t,&dir);
//        D(s);D(t);D(dir);E;
        int len=t-s+1;
        if(dir==1) for(int i=1;i<=m;i++) dp(n,i,len,dir);
        if(dir==2) for(int i=1;i<=m;i++) dp(1,i,len,dir);
        if(dir==3) for(int i=1;i<=n;i++) dp(i,m,len,dir);
        if(dir==4) for(int i=1;i<=n;i++) dp(i,1,len,dir);
    }
    printf("%d",ans);
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

BZOJ3316
题意
n(n<=1e5)个非负整数排成一圈，可以选出一个长度在[L,R]间，且为偶数的区间，得到区间平均值的贡献。求最大贡献。
题解
首先，通过倍长数组的方式，避开对环形的讨论。
其次，求最大平均值，可采用二分答案。
然后，为了高效的验证当前答案是否可行，可对序列的前缀和数组维护单调递增队列（这样队首元素最小）。
最后，因为区间长度必须为偶数，所以对奇偶下标分别维护一个单调队列。
PS：
队列中存储可行的队首下标，每次循环时，判断当前元素i是否可以作为队尾下标，更新答案，并将i-L+1加入队列。这样避免了[1,L-1]的边界讨论，还保证了首尾元素相距大于等于L。
答案虽然要求输出既约分数，但仍旧可以二分答案，只要在找到可行解的时侯记录分子分母即可。
题解链接 https://www.cnblogs.com/CQzhangyu/p/7536452.html
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=2e5+5; //倍长空间
const int INF=0x3f3f3f3f;
int n,L,R;
ll A[maxn],S[maxn];
double a[maxn],s[maxn];
ll ans1,ans2;
ll gcd(ll x,ll y){
    return !y?x:gcd(y,x%y);
}
int q1[maxn],q2[maxn],head1,tail1,head2,tail2;
void init(){
    head1=head2=1,tail1=tail2=0;
}
bool check(double mid){
    init();
    for(int i=1;i<=n<<1;i++){ //倍长数组 处理环形
        a[i]=(double)A[i]-mid;
        s[i]=s[i-1]+a[i];
//        cout<<s[i]<<" ";
    }
//    E;
    q1[++tail1]=0;
    for(int i=L;i<=n<<1;i++){ //从第L个开始考虑 避免边界的讨论
        while(head1<=tail1&&i-q1[head1]>R) head1++;
        while(head2<=tail2&&i-q2[head2]>R) head2++;
        if(!(i&1)&&head1<=tail1&&s[i]-s[q1[head1]]>=0){ //(q1[head1],i]
            ans1=S[i]-S[q1[head1]],ans2=i-q1[head1];
            ll d=gcd(ans1,ans2);
            ans1/=d,ans2/=d;
//            D(i);D(q1[head1]);E;
            return true;
        }
        if((i&1)&&head2<=tail2&&s[i]-s[q2[head2]]>=0){ //(q2[head2],i]
            ans1=S[i]-S[q2[head2]],ans2=i-q2[head2];
            ll d=gcd(ans1,ans2);
            ans1/=d,ans2/=d;
//            D(i);D(q2[head2]);E;
            return true;
        }
        //入队的元素是i-L+1，这就保证队列中首尾元素差大于等于L，即队列中存储可行的队首
        if(!(i-L+1&1)){
            while(head1<=tail1&&s[i-L+1]<=s[q1[tail1]]) tail1--;
            q1[++tail1]=i-L+1; 
        }
        else{
            while(head2<=tail2&&s[i-L+1]<=s[q2[tail2]]) tail2--;
            q2[++tail2]=i-L+1;
        }
    }
    return false;
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("BZOJ3316.in","r",stdin);
    scanf("%d%d%d",&n,&L,&R);
    double l,r;
    for(int i=1;i<=n;i++){
        scanf("%lld",&A[i]);
        A[i+n]=A[i];
        l=min(l,(double)A[i]);
        r=max(r,(double)A[i]);
    }
    for(int i=1;i<=n<<1;i++) S[i]=S[i-1]+A[i];
/*
    for(int j=1;j<=n<<1;j++) cout<<A[j]<<" ";
    E;
*/
    for(int i=1;i<=50;i++){
        double mid=(l+r)/2;
        if(check(mid)) l=mid;
        else r=mid;
    }
    if(ans2==0||ans2==1) printf("%lld",ans1);
    else printf("%lld/%lld",ans1,ans2);
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

BZOJ4476
题意
给定长度为n(n<=50000)的序列，可以选出一个长度在[L,R]间的区间，得到\frac { 区间最大值-区间最小值}{区间长度}的贡献。求最大贡献。
题解
可以发现一定是最大值和最小值都在两端时最优，但可能长度超出限制。
答案可能由两部分组成：
1.长度为L
2.最大值和最小值在两端
第一种情况是单调队列模板。（开两个队列，分别维护区间最大值和最小值）
第二种情况是个经典的01分数规划。
二分答案mid，设最小值为v[j],最大值为v[i]，所以式子就变成：
v[i]-v[j]-(i-j+k)*mid>=0或v[i]-v[j]-(j-i+k)*mid>=0
然后分开讨论，第一个变成判断(v[j]-j*mid)-(v[i]-i*mid)的最大值是否>=mid*k，第二个变成判断(v[i]+i*mid)-(v[j]+j*mid)的最大值是否>=mid*k。
于是用单调队列维护第一个式子中v[i]-i*mid的最小值和第二个式子中v[i]+i*mid的最大值，然后判断对应的表达式最大值是否>=mid*k即可。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=50000+5;
const int INF=0x3f3f3f3f;
const double eps=1e-7;
int T;
int n,k,L,R;
double a[maxn];
double ans1,ans2;
int head1,tail1,head2,tail2,q1[maxn],q2[maxn];
void init(){
    ans1=0,ans2=0;
}
void init1(){
    head1=head2=1,tail1=tail2=0;
}
int head3,tail3,q3[maxn];
void init2(){
    head3=1,tail3=0;
}
void solve1(){
    init1();
    for(int i=1;i<=n;i++){
        while(head1<=tail1&&i-q1[head1]>=L) head1++;
        while(head2<=tail2&&i-q2[head2]>=L) head2++;
        while(head1<=tail1&&a[q1[tail1]]<a[i]) tail1--;
        while(head2<=tail2&&a[q2[tail2]]>a[i]) tail2--;
        q1[++tail1]=i;
        q2[++tail2]=i;
        ans1=max(ans1,(a[q1[head1]]-a[q2[head2]])/(L-1+k));
    }
//    D(ans1);E;
}
double temp[maxn];
bool check(double mid){
    //5 3 1 2 4
//    D(mid);
    double res=-1; //这里不能初始化为0 否则会有误差 造成WA
    init2();
    for(int i=1;i<=n;i++) temp[i]=a[i]-i*mid;
    for(int i=L+1;i<=n;i++){
        while(head3<=tail3&&i-q3[head3]>=R) head3++;
        while(head3<=tail3&&temp[q3[tail3]]>=temp[i-L]) tail3--;
        q3[++tail3]=i-L;
        res=max(res,temp[i]-temp[q3[head3]]); 
    }
//    for(int i=1;i<=n;i++) cout<<temp[i]<<" ";
//    D(res);
    init2();
    for(int i=1;i<=n;i++) temp[i]=a[i]+i*mid;
    /*
    for(int i=n-L;i;i--){
        while(head3<=tail3&&q3[head3]-i>=R) head3++;
        while(head3<=tail3&&temp[q3[tail3]]>=temp[i+L]) tail3--;
        q3[++tail3]=i+L;
        res=max(res,temp[i]-temp[q3[head3]]); 
    }
    */
    for(int i=L+1;i<=n;i++){
        while(head3<=tail3&&i-q3[head3]>=R) head3++;
        while(head3<=tail3&&temp[q3[tail3]]<=temp[i-L]) tail3--;
        q3[++tail3]=i-L;
        res=max(res,temp[q3[head3]]-temp[i]);
    }
//    for(int i=1;i<=n;i++) cout<<temp[i]<<" ";
//    D(res);E;
    return res>=k*mid;
}
void solve2(){
    double l=0,r=1e3;
    while(r-l>eps){
        double mid=(l+r)/2;
        if(check(mid)) l=mid;
        else r=mid;
    }
    ans2=l;
//    D(ans2);E;
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("BZOJ4476.in","r",stdin);
    scanf("%d",&T);
    while(T--){
        init();
        scanf("%d%d%d%d",&n,&k,&L,&R);
        for(int i=1;i<=n;i++) scanf("%lf",&a[i]);
        solve1();
        solve2();
        printf("%.4lf\n",max(ans1,ans2));
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

相关文章

  • DP训练——单调队列优化DP

    单调队列DP HDU5945题意给定整数，存在如下两种操作。1.2.如果 求让变为的最小操作次数。题解状态定义：表...

  • POJ_1821 Fence

    1.题目相关 标签：DP 单调队列优化 题目地址：http://poj.org/problem?id=1821 题...

  • BZOJ_2442 修剪草坪

    1.题目相关 标签：DP 单调队列优化 题目地址：不是VIP没法看。。。。 题目大意：给定N和K，表示有N个数，在...

  • DP训练——斜率优化DP

    斜率优化DP 斜率优化DP涉及到的模型较多，在编写习题题解前，先做出如下规律总结。 如何识别斜率优化DP 按照正常...

  • 线性dp+单调队列

    题目：洛谷P5858 「SWTR-03」Golden Sword[https://www.luogu.com.cn...

  • DP的五类优化(2) - 快速幂，四边形不等式

    在上一章中，我们介绍了基于单调队列和二进制DP的优化。今天我们来看另外3类，斜率优化，四边形不等式，快速幂优化。 ...

  • DP训练——线段树优化DP

    线段树优化DP HDU3698题意给定的矩阵和，须从矩阵的每行选择一个数字，使得数字和最小。选择时须保证前后选择的...

  • DP训练——树状数组优化DP

    树状数组DP BZOJ1264题意给出两个长度均为的数字序列，求。数据保证每个序列中，到共个数字每个必然出现次。题...

  • 决策单调性优化——另一种DP优化利器

    今天，我们来介绍另一种DP优化方法——决策单调行优化。 决策单调性优化与斜率优化有相似之处，但又有不同之处。 相似...

  • 前缀和优化DP

    前缀和优化 DP 当 DP 转移方程是如下形式的时候 计算 dp[i] 时需要一步求和 sum(dp[a..b])...

网友评论

    本文标题：DP训练——单调队列优化DP

    本文链接：https://www.haomeiwen.com/subject/rbwdqhtx.html

    延伸阅读

    深度阅读

    • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

    栏目导航

    热点阅读

    动态规划

    关于我们|服务条款|联系我们|DP训练——单调队列优化DP|投稿指南|网站地图|RSS订阅|排版工具|手机版

    提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

    Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

    备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

    本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

    所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！