P1081

Aryper · 2021-07-31 11:47:28 · 个人记录

[NOIP2012 提高组] 开车旅行

DP 倒还好，主要是 set 还有倍增。。。

然后我们发现只要能在 O(\log n) 下单次解决第二个问题，第一个问题实质上已经解决了（因为可以在 O(n\log n) 下暴力比较）。。。

想要在 O(\log n) 下单次解决第二个问题，思考倍增优化 DP 。

定义 f_i,_j,_k 表示走 2^i 天，从 j 出发，开始由 A (k=0) 或 B （k=1） 驾驶到达的地点。

定义 da_i,_j,_k 表示 2^i 天，从 j 出发，开始由 A (k=0) 或 B （k=1） 驾驶，其中 A 驾驶的路程。

定义 db_i,_j,_k 表示 2^i 天，从 j 出发，开始由 A (k=0) 或 B （k=1） 驾驶，其中 B 驾驶的路程。

然后我们就可以思考这个转移方程。

因为驾驶天数在非 2^0=1 时，天数是偶数天，所以转移时开始驾驶的人就不用换，反之是要切换的。

那么有如下转移：

1. 对于 i=1 时，

2. 对于 i\not=1 时，

然后我们开始思考初始化。

显然 i=0 时转移不到，所以把所有 i=0 的状态赋好初值。

我们预先处理这些状态的复杂度是 O(n\log n) 。然后就可以使用倍增来模拟解决第二个问题。

我们现在只需要考虑状态初值的赋法。

那么我们需要预先处理出每个地点的第二近地和第一近地，为了求出这个我们使用 set 来维护。

显然在倒序向其中插入点后，我们要找的两个点必然存在于这个点的：1.前驱；2.后继；3.前驱的前驱；4.后继的后继；这四个地方都求出来的复杂度是 O(\log n) 的。

那么我们知道最近的点一定在 1 或 2 中，找到最近的点之后我们分类讨论：

1. 如果是 1 ，那么次近的点为 2 或 3 ，而 4 是不可能的。

2. 如果是 2 ，那么次近的点为 1 或 4 ，而 3 是不可能的。

这样之后我们就求出了每一个点在 A 或 B 行驶之后的下一个地点，中间的距离也可以求出。但是要注意一开始集合中点不够所以加两个极大值的点和两个极小值的点。

这样的话我们的初始化就简单了。

然后这里 dis 是 distance （距离）的缩写， dest 是 destination （目的地）的缩写。至于 da_0,_j,_1 和 db_0,_j,_0 ，它们的值都是 0 ，所以就不用管了。

然后没了。

时间复杂度 O((m+n)\log n) 。

代码：

#include<iostream>
#include<cstdio>
#include<set>
#include<cmath>
#define ll long long
using namespace std;

const ll N=1e5,M=1e5,inf=1e11;

struct node{
    ll id,al;
    bool operator < (const node& rhs) const{
        if(al==rhs.al) return id<rhs.id;
        return al<rhs.al;
    }
}cur,tmp1,tmp2,st;

multiset<node> q;

ll n,x0,m,ans_id,dis_a,dis_b,dest_a,dest_b;

ll s[M+5],x[M+5],h[N+5],f[25][N+5][2],da[25][N+5][2],db[25][N+5][2];

double tmp,ans;

void solve(ll _s,ll _x) {
    ll p=_s;
    dis_a=0;dis_b=0;
    for(ll i=18;i>=0;i--) {
        if(f[i][p][0]&&dis_a+dis_b+da[i][p][0]+db[i][p][0]<=_x) {
            dis_a+=da[i][p][0];dis_b+=db[i][p][0];
            p=f[i][p][0];
        }
    }
}

void init() {
    h[0]=inf;h[n+1]=-inf;
    st.id=0;st.al=inf;q.insert(st);q.insert(st);
    st.id=n+1;st.al=-inf;q.insert(st);q.insert(st);
    for(ll i=n;i>=1;i--) {
        cur.id=i;cur.al=h[i];q.insert(cur);
        set<node>::iterator p=q.lower_bound(cur);
        --p;tmp1=*p;
        ++p;++p;tmp2=*p;
        --p;

        if(abs(tmp2.al-h[i])>=abs(tmp1.al-h[i])) {
            dest_b=tmp1.id;
            --p;--p;
            if(abs(tmp2.al-h[i])>=abs((*p).al-h[i])) {
                dest_a=(*p).id;
            }
            else {
                dest_a=tmp2.id;
            }
        }
        else {
            dest_b=tmp2.id;
            ++p;++p;
            if(abs((*p).al-h[i])>=abs(tmp1.al-h[i])) {
                dest_a=tmp1.id;
            }
            else {
                dest_a=(*p).id;
            }
        }

        f[0][i][0]=dest_a;f[0][i][1]=dest_b;
        da[0][i][0]=abs(h[i]-h[dest_a]);
        db[0][i][1]=abs(h[i]-h[dest_b]);
    }

    for(ll i=1;i<=18;i++) {
        for(ll j=1;j<=n;j++) {
            for(ll k=0;k<=1;k++) {
                if(i==1) {
                    f[1][j][k]=f[0][f[0][j][k]][k^1];
                    da[1][j][k]=da[0][j][k]+da[0][f[0][j][k]][k^1];
                    db[1][j][k]=db[0][j][k]+db[0][f[0][j][k]][k^1];
                }
                else {
                    f[i][j][k]=f[i-1][f[i-1][j][k]][k];
                    da[i][j][k]=da[i-1][j][k]+da[i-1][f[i-1][j][k]][k];
                    db[i][j][k]=db[i-1][j][k]+db[i-1][f[i-1][j][k]][k];
                }
            }
        }
    }
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    ll y=10,len=1;
    while(y<=x) {y*=10;len++;}
    while(len--) {y/=10;putchar(x/y+48);x%=y;}
}

void writeln(ll x) {
    if(x<0) {x=-x;putchar('-');}
    ll y=10,len=1;
    while(y<=x) {y*=10;len++;}
    while(len--) {y/=10;putchar(x/y+48);x%=y;}
    putchar('\n');
}

int main() {

    n=read();

    for(ll i=1;i<=n;i++) {
        h[i]=read();
    }

    x0=read();

    m=read();

    for(ll i=1;i<=m;i++) {
        s[i]=read();x[i]=read();
    }

    init();

    ans=inf;

    for(ll i=1;i<=n;i++) {
        solve(i,x0);
        tmp=(double)dis_a/(double)dis_b;
        if(tmp<ans) {
            ans=tmp;ans_id=i;
        }
        else
        if(tmp==ans&&h[ans_id]<h[i]) ans_id=i;
    }

    writeln(ans_id);

    for(ll i=1;i<=m;i++) {
        solve(s[i],x[i]);
        write(dis_a);putchar(' ');writeln(dis_b);
    }

    return 0;
}