P1081 开车旅行

TEoS · 2019-06-10 13:21:39 · 题解

这道题主要的难点在于预处理以及DP的设计，实现起来难度不会太大，主要是思路。本文会详细地对思路进行讲解，思路和代码会尽量清晰，希望对大家有帮助。

本文的思路与大部分大佬的思路基本相同，主要是带来更详细的讲解和更清晰的实现。

关于题意，样例说明解释得很清楚，如果没有读懂的结合题目多读几遍就懂了，这里就不再赘述。

先补充几点：

• STL-set的部分操作

实现流程：倍增优化DP

思路：DP递推出与问题相关的决策，利用倍增优化求解。

具体实现流程：

1、输入

输入就不多说了吧，直接上代码。

输入代码：

int n,m,x0;
int h[N],s[N],x[N];

cin>>n;
for(int i=1;i<=n;i++)
    scanf("%d",&h[i]);
cin>>x0>>m;
for(int i=1;i<=m;i++)
    scanf("%d%d",&s[i],&x[i]);

2、预处理

首先预处理出从每个城市出发，小A和小B开车分别会到达的下一个城市。分析题意后很容易知道，对于当前编号为x的城市，所求的就是编号x+1~n的城市构成的集合中距离城市x最近和次近的城市。这个问题可以用平衡树或双向链表求解。由于本人太菜，不会写双向链表，所以在这里用STL的set实现，想要了解双向链表实现的大佬们请看别的题解。

如何用平衡树实现？显然，在由编号x~n的城市构成的平衡树上，离城市x最近的一定是x的前驱或后继，次近的一定在x的前驱、后继、前驱的前驱和后继的后继当中。我们只要取出这些节点，分别比较与x的距离，找到最小的两个即可。

在这里有几点要注意的：

• 由于查找时会涉及到x周围的四个节点，因此在一开始要先向平衡树分别插入2个极大值和极小值节点，以免越界。
• 由于在平衡树中每个城市需要保存编号和海拔两个数据，因此在使用set时要重载运算符来保证节点set中的顺序。
• set的迭代器只支持++和--两个操作，不能使用其它运算。

预处理代码：

struct City
{
    int id,al;//identifier编号,altitude海拔
    friend bool operator < (City a,City b)
    {
        return a.al<b.al; 
    }//重载运算符，按照海拔升序
};//存储城市信息

multiset<City> q;//支持集合内重复元素的set

h[0]=INF,h[n+1]=-INF;
City st;//start
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);//插入4个初始节点
for(int i=n;i;i--)//倒序插入，保证set内只有编号x~n的城市
{
    int ga,gb;//分别表示从当前城市出发小A和小B开车的下一站
    City now;
    now.id=i,now.al=h[i];
    q.insert(now);//插入当前城市
    set<City>::iterator p=q.lower_bound(now);//迭代器，在这里指向now节点
    p--;
    int lt=(*p).id,lh=(*p).al;//last前驱
    p++,p++;
    int ne=(*p).id,nh=(*p).al;//next后继
    p--;
    if(abs(nh-h[i])>=abs(h[i]-lh))//若前驱更近
    {
        gb=lt;
        p--,p--;//找到前驱的前驱
        if(abs(nh-h[i])>=abs(h[i]-(*p).al))//若前驱的前驱更近
            ga=(*p).id;
        else//若后继更近
            ga=ne;
    }
    else//若后继更近
    {
        gb=ne;
        p++,p++;//找到后继的后继
        if(abs((*p).al-h[i])>=abs(h[i]-lh))//若前驱更近
            ga=lt;
        else//若后继的后继更近
            ga=(*p).id;
    }
}

3、倍增优化DP

本题中DP需要用到三个数组：

其中k=0表示小A先开车，k=1表示小B先开车。

转移方程还是比较好想的，在DP时，i作为阶段，j作为状态，对于每个天数2^i，分别从前后两半时间转移过来即可。在转移时要注意，因为2^0=1是奇数，因此在转移到2^1时，前后两半时间先开车的人不一样，因此要独立出来转移；其余的状态转移方程均相同。

DP初值：

• f_{0,j,0}=ga_j,f_{0,j,1}=gb_j
• da_{0,j,0}=dist_{j,ga_j},da_{0,j,1}=0
• db_{0,j,0}=0,db_{0,j,1}=dist_{j,gb_j}

其中dist_{x,y}表示城市x到城市y的距离

以上的初值设置很好理解，请读者结合数组的定义自己思考。

初值的设置为了方便可以直接在上面的预处理过程中进行。

DP初值赋值代码：

int f[20][N][5],da[20][N][5],db[20][N][5];  

for(int i=n;i;i--)
    {
        ...//预处理
        f[0][i][0]=ga,f[0][i][1]=gb;
        da[0][i][0]=abs(h[i]-h[ga]);
        db[0][i][1]=abs(h[i]-h[gb]);
    }

状态转移方程：

当i=1时：

• f_{1,j,k}=f_{0,f_{0,j,k},1-k}
• da_{1,j,k}=da_{0,j,k}+da_{0,f_{0,j,k},1-k}
• db_{1,j,k}=db_{0,j,k}+db_{0,f_{0,j,k},1-k}

当i>1时：

• 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}

具体原理请读者自己思考，下面的代码中也会进行讲解。

DP转移代码：

for(int i=1;i<=18;i++)
        for(int j=1;j<=n;j++)
            for(int k=0;k<2;k++)
                if(i==1)//此时后半段先开车的人和整段先开车的人不同
                {
                    f[1][j][k]=f[0][f[0][j][k]][1-k];//整段的路程即后半段到达的路程，后半段的起点即前半段的终点
                    da[1][j][k]=da[0][j][k]+da[0][f[0][j][k]][1-k];//整段小A行驶的路程即前半段和后半段小A行驶的路程之和
                    db[1][j][k]=db[0][j][k]+db[0][f[0][j][k]][1-k];//整段小B行驶的路程即前半段和后半段小B行驶的路程之和 
                }
                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];
                }

4、求解问题1

很显然，要知道小A和小B行驶路程的比值，只要知道他们分别行驶的路程就可以了。这里定义一个函数calc(S,X)求解从城市S出发，最多行驶X公里，小A和小B分别行驶了多少距离。

通过上面DP推出的三个数组，calc函数的实现就不难了，只要倍增模拟前进即可。

具体实现：

1. 初始化p=S,la=0,lb=0
2. 倒序循环i=\log n~0，对于每个i，若从当前的p行驶2^i天仍不超过X，则前进；即若la+lb+da_{i,p,0}+db_{i,p,0}\leq X，则令la+=da_{i,p,0},lb+=db_{i,p,0},p=f_{i,p,0}。判断时还要注意一个条件，因为要保证不超过最后一个城市，即不越界，因此要特判当前枚举的终点在n个城市之内，其实只要f_{i,p,0}>0就满足条件。
3. 第2步结束后，la和lb就是所求的答案，分别表示小A和小B行驶的路程。