【BZOJ 2216】【POI 2011】[动态规划][决策点单调优化]Lightning Conductor

Advertisement

题目描述

已知一个长度为n的序列a1,a2,…,an。
对于每个1<=i<=n,找到最小的非负整数p满足对于任意的j,aj≤ai+p−abs(i−j)−−−−−−−−√

题目解析

转化一下原式就可以把它变成p≥aj+abs(i−j)−−−−−−−−√−ai
即对于每一个i求p=max(aj+abs(i−j)−−−−−−−−√)−ai
因为y=x√这个函数的Δy=x√−x−1−−−−√是递减的(可以求导证明)
于是对于j<k,若aj+abs(i−j)−−−−−−−−√≤ak+abs(i−k)−−−−−−−−√则决策点k永远优于决策点j;
而若aj+abs(i−j)−−−−−−−−√>ak+abs(i−k)−−−−−−−−√,随着i的增大,k后可能比j优。

(下文中设val(i,pos)=a[pos]+i−pos−−−−−−√ | i>pos)

解法一:我们不妨用set维护一个单调队列,使得对于当前i,val(i,que[j])是不上升的。然后考虑加入决策点i,若aque[r]+abs(i−que[r])−−−−−−−−−−−√≤ai直接弹掉队尾,否则二分que[r]会在哪里被i超越,把点对塞进那个点的vector里。
然后枚举在i有哪些点对相互超越,然后在set中维护一下就行了。

解法二:(HCX大佬想出来的,我反正只能抄抄POPOQQQ大爷的代码。)
类似于解法一,我们维护一个三元组单调队列(pos,lef,rig),表示决策点pos目前看来对于区间(lef,rig)最优,加入决策点i时,若val(lefr,posr)<=val(lefr,i),则posr可以舍弃,否则可以在lefr到rigr+1间二分一下lefi,更新一下就行了。

最后时间分别是22524ms和4000ms,感到自己深深地垃圾。

代码

代码一:(set实现)

/**************************************************************
    Problem: 2216
    User: bzjudge2
    Language: C++
    Result: Accepted
    Time:22524 ms
    Memory:28800 kb
****************************************************************/

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<set>
using namespace std;

#define MAXN 500000
#define MAXM
#define INF 0x3f3f3f3f
typedef long long int LL;

template<class T>
void Read(T &x){
    x=0;char c=getchar();bool flag=0;
    while(c<'0'||'9'<c){if(c=='-')flag=1;c=getchar();}
    while('0'<=c&&c<='9'){x=x*10+c-'0';c=getchar();}
    if(flag)x=-x;
}

int n;
int a[MAXN+10];
double VAL(int i,int pos){return (double)a[pos]+sqrt(i-pos);}

int find(int x,int y){//二分x在什么时候被y超过
    int l=y+1,r=n+1,mid;
    int ans=n+1;
    while(l<=r){
        mid=(l+r)>>1;
        if(VAL(mid,x)<VAL(mid,y)){
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }

    return ans;
}

set<int>op;
vector< pair<int,int> >s[MAXN+10];
void work(int *dp){
    for(int i=1;i<=n+1;++i)s[i].clear();
    op.clear();

    set<int>::iterator it,tmp;
    for(int i=1;i<=n;++i){
        //维护后缀单调
        while(!op.empty()){//弹弹弹,弹走鱼尾纹...
            it=op.end(),--it;
            if(VAL(i,*it)<=a[i])
                op.erase(it);
            else break;
        }

        if(!op.empty()){//准备弹飞
            it=op.end(),--it;
            s[find(*it,i)].push_back(make_pair(*it,i));
        }

        op.insert(i);

        //维护中间单调
        while(!s[i].empty()){//看看当前可以弹飞那些决策点
            int x=s[i].back().first,y=s[i].back().second;
            s[i].pop_back();

            if(op.find(y)==op.end())//y已被弹出(已有更优解)
                continue;//不需替换
            if((it=op.find(x))==op.end())//x已被弹出...防卡死
                continue;

            while(true){
                if(VAL(i,*it)<=VAL(i,y)){//能弹就使劲弹
                    if(it==op.begin()){
                        op.erase(it);
                        break;
                    }
                    else{
                        tmp=it--;
                        op.erase(tmp);
                    }
                }
                else{//不能弹出,再次准备
                    s[find(*it,y)].push_back(make_pair(*it,y));
                    break;
                }
            }
        }

        //取出最优解
        it=op.begin();
        dp[i]=a[*it]+ceil(sqrt(i-*it))-a[i];
    }
}

int dpfront[MAXN+10],dpback[MAXN+10];
int main(){
    Read(n);
    for(int i=1;i<=n;++i)Read(a[i]);

    work(dpfront);

    for(int i=1;i<=(n>>1);++i)
        swap(a[i],a[n-i+1]);

    work(dpback);

    for(int i=1;i<=n;++i)
        printf("%d\n",max(dpfront[i],dpback[n-i+1]));
}

代码二:(数组实现)

/**************************************************************
    Problem: 2216
    User: bzjudge2
    Language: C++
    Result: Accepted
    Time:4000 ms
    Memory:13020 kb
****************************************************************/

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;

#define MAXN 500000
#define MAXM
#define INF 0x3f3f3f3f
typedef long long int LL;

template<class T>
void Read(T &x){
    x=0;char c=getchar();bool flag=0;
    while(c<'0'||'9'<c){if(c=='-')flag=1;c=getchar();}
    while('0'<=c&&c<='9'){x=x*10+c-'0';c=getchar();}
    if(flag)x=-x;
}

int n;
int a[MAXN+10];

const double EPS = 1e-6;
int Sign(const double x){
    if(x>EPS)return 1;
    else if(x<-EPS)return -1;
    else return 0;
}

double VAL(int i,int pos){return (double)a[pos]+sqrt(i-pos);}

//单调队列{
int que[MAXN+10];//决策点位置(按决策区间的左端点单调)
int l[MAXN+10],r[MAXN+10];//决策点可以覆盖的最优解范围
int ql,qr;
//}

void work(int *dp){
    ql=1,qr=0;

    for(int i=1;i<=n;++i){
        while(ql<=qr&&r[ql]<i)++ql;//当前决策点已过期
        if(ql<=qr)l[ql]=max(l[ql],i);//更新最优决策点决策区间

        //加点&&维护单调性
        if(ql>qr||VAL(n,que[qr])<VAL(n,i)){//如果决策点i可以代替决策点que[r]
            //向单调队列中加点
            while(ql<=qr&&VAL(l[qr],que[qr])<VAL(l[qr],i))
                --qr;//若i比que[qr]在l[qr]端点都要优,que[qr]是一定可以抛弃的
            if(ql>qr)que[++qr]=i,l[qr]=i,r[qr]=n;//若队列为空
            else{//二分超越点&&更新
                int pos=r[qr]+1;
                int ll=l[qr],rr=r[qr]+1,mid;
                while(ll<=rr){
                    mid=(ll+rr)>>1;
                    if(VAL(mid,que[qr])<=VAL(mid,i)){
                        pos=mid;
                        rr=mid-1;
                    }
                    else ll=mid+1;
                }

                r[qr]=pos-1;
                que[++qr]=i,l[qr]=pos,r[qr]=n;
            }
        }

        dp[i]=a[que[ql]]+ceil(sqrt(i-que[ql]))-a[i];//得到答案
    }
}

int dpfront[MAXN+10],dpback[MAXN+10];
int main(){
    Read(n);
    for(int i=1;i<=n;++i)Read(a[i]);

    work(dpfront);

    for(int i=1;i<=(n>>1);++i)
        swap(a[i],a[n-i+1]);

    work(dpback);

    for(int i=1;i<=n;++i)
        printf("%d\n",max(dpfront[i],dpback[n-i+1]));
}

Similar Posts:

  • 【BZOJ】3039: 玉蟾宫(DP/单调栈)

    http://www.lydsy.com/JudgeOnline/problem.php?id=3039 每次看到我的提交都有点淡淡的忧伤T_T.. 看到此题我想到用前缀和维护点ij向左和向上能拓展的最大长度,然后设状态f(i, j, 0)表示ij这个点为最大矩形的右下角时的长(横的),f(i, j, 1)表示ij这个店为最大矩形右下角时的宽(竖的),然后决策就是取点(i-1, j-1)的f值拓展一层为ij的,找到一个可行最大解. 过了几个样例我以为就能过了0.0没有认真考虑,,所以造成了前面2

  • bzoj 2096: [Poi2010]Pilots (二分答案+单调队列)

    2096: [Poi2010]Pilots Time Limit: 30 Sec  Memory Limit: 162 MB Submit: 719  Solved: 368 [Submit][Status][Discuss] Description Tz又耍畸形了!!他要当飞行员,他拿到了一个飞行员测试难度序列,他设定了一个难度差的最大值,在序列中他想找到一个最长的子串,任意两个难度差不会超过他设定的最大值.耍畸形一个人是不行的,于是他找到了你. Input 输入:第一行两个有空格隔开的整数k

  • [BZOJ 3747] [POI 2015] Kinoman【线段树】

    Problem Link : BZOJ 3747 题解:ZYF-ZYF 神犇的题解 解题的大致思路是,当区间的右端点向右移动一格时,只有两个区间的左端点对应的答案发生了变化. 从 f[i] + 1 到 i 的区间中的答案增加了 W[A[i]], 从 f[f[i]] + 1 到 f[i] 的区间的答案减少了 W[A[i]] ,其余区间的答案没有发生变化. 那么就是线段树的区间修改和区间最值查询. 代码如下: #include <iostream> #include <cstdio>

  • 动态规划--最长单调递增子序列

    问题:找出一个n个数的序列X中最长的单调递增子序列. 分析1: 这里描述一个O(n^2)的算法,令c[i]表示:在a[0->i]中,当以a[i]为单调递增子序列最后一个元素时,所得最长单调递增子序列的长度.所以,我们可以得到递推式: 代码: #include <iostream> #define MAXLENGTH 1000 using namespace std; /** * @brief Get the longest increasing subsequence. The time

  • [BZOJ 2086]Poi 2010 Blocks

    实战的时候逗比的使劲儿优化O(mnlgn)的算法,搞得吐血后才多对1个点,还是有2个点毫无压力的T啦 然后看了题解才发现自己逗比到一定境界了.... 我们的目的就是找到最小的j,使得j<i且s[j]<s[i].只分析到这是不够的,因为我们不是要求每一个i对应的j,只要求出最大的j-i. 这样我们就可以去掉lgn了.把s最成一个单调下降的序列,现在队列求出n对应的j(很明显j存在于这个下降序列中),我们发现在找n-1对应的j中,若想更新答案,其对应的j必定比n对应的j小! 因此我们只用两个指针不

  • Bzoj 1222: [HNOI2001]产品加工 动态规划

    1222: [HNOI2001]产品加工 Time Limit: 15 Sec Memory Limit: 162 MB Submit: 486 Solved: 298 [Submit][Status][Discuss] Description 某加工厂有A.B两台机器,来加工的产品可以由其中任何一台机器完成,或者两台机器共同完成.由于受到机器性能和产品特性的限制,不同的机器加工同一产品所需的时间会不同,若同时由两台机器共同进行加工,所完成任务又会不同.某一天,加工厂接到n个产品加工的任务,每个

  • BZOJ 1025 SCOI2009 游戏 动态规划

    标题效果:特定n.行定义一个替代品1~n这种更换周期发生后,T次要(T>0)返回到原来的顺序 找到行的所有可能的数 循环置换分解成若干个,然后行位移数是这些周期的长度的最小公倍数 因此,对于一些,是将这个数分解质因数.令x=p1^a1*p2^a2*...*pk^ak.若p1^a1+p2^a2+...+pk^ak<=n,则x就是可能的排数 分组背包就可以 令f[i][j]表示用前i个质数,和为j能得出的数的数量 每组的物品是pi^1~pi^ai 时间复杂度O(n/lgn*logn*n)=O(n^

  • BZOJ 2326 HNOI 2011 数学作业 矩阵乘法

    题目大意 求一个这样的数:"12345678910111213--"对m取模的值. 思路 观察这个数字的特点,每次向后面添加一个数.也就是原来的数乘10^k之后在加上一个数.而且处理每个数量级的时候是相似的.所以就可以用矩阵乘法来加速.我构造的矩阵是这样的. [当前数字累加数字1]×⎡⎣⎢数量级10011001⎤⎦⎥=[新的数字累加数字+11] CODE #include <cstdio> #include <cstring> #include <iost

  • BZOJ 3295 CQOI 2011 动态逆序对 线段树套Treap

    题目大意:给出一个数列,每次从这个序列中删掉一个数字,问每次删之前逆序对的数量是多少. 思路:这个题用CDQ分治是飞快的,然而我不知道怎么写..于是就朴素的写了树套树.然后就朴素的被卡常了 内层用一个线段树.这个线段树不修改,一开始就要建好,然后线段树的每一个节点维护一个平衡树,存的是线段树存的区间中所有的值. 一开始先算一下逆序对数,然后每次删点的时候,先查询在这个点之前有多少大于他的,后面有多少小于他的,总的逆序对中将这些减掉.这个过程通过树套树不难实现. CODE(交了这个代码T掉的,请选

  • BZOJ 2760 JLOI 2011 小A的烦恼 模拟

    题目大意:小A有一些烦恼,现在要求你去给他解决一下. 思路:语法基础题. CODE: #include <cstdio> #include <string> #include <cstring> #include <iostream> #include <algorithm> #define MAX 1010 using namespace std; int total,m; string ans[MAX],name; int cnt[MAX];

Tags: