P1016 旅行家的预算

· · 题解

看到这个数据范围，本蒟蒻马上就想到了搜索 毕竟万物皆可搜索嘛

所有的加油站和起点终点都是在一条直线上的，我们可以把它们看做N+2个节点，起点编号为0，终点编号为N+1。对于每个节点，枚举在该处加油的多少。我们可以发现，加油量只有两种情况，一是刚好可以到达任何一个节点，二就是加满整个油箱。因此枚举也变得可行了。而对于枚举到的状态，进行搜索继续枚举，直到到达终点为止。

对于搜索函数，我们传入三个量，分别为该节点的编号，当时的油量和当时的花费。我们从该节点开始枚举节点i，直到i==N+1结束，枚举该节点加油到刚好可以行驶到i节点的状态。这样讲可能有点乱，上代码更清楚一点：

void get(int x,double s,double m)//分别表示编号、油量和花费
{
    if(s<0 || s>c)
        return ;//若油箱的油不符合实际，则返回
    if(x==n+1)
    {
        ans=min(ans,m);
        return ;
    }//到达终点则更新答案
    for(int i=x;i<=n+1 && (cn[i][0]-cn[x][0])/d2<=c;i++)
        if((cn[i][0]-cn[x][0])/d2<=s)
            get(x+1,s-(cn[x+1][0]-cn[x][0])/d2,m);//若到达节点i所需的油比当前的油还少，则不用加油
        else
            get(x+1,(cn[i][0]-cn[x][0])/d2-(cn[x+1][0]-cn[x][0])/d2,m+((cn[i][0]-cn[x][0])/d2-s)*cn[x][1]);//若当前的油不够开到节点i，则加到刚好可以开到
    get(x+1,c-(cn[x+1][0]-cn[x][0])/d2,m+(c-s)*cn[x][1]);//加满油箱

}

最后说一下输出，题目要求是四舍五入保留两位小数输出，但经过本蒟蒻的试验，四舍五入是不行的，直接输出即可（为何如此毒瘤），用printf方便又快捷：

if(ans==INF)//若没有更新答案说明不能到达终点
        cout<<"No Solution";
    else
        printf("%.2lf",ans);

好了，最后上一下完整的代码：

#include<iostream>
#include<cstdio>
using namespace std;
double d1,c,d2,p,ans=1e6,cn[10][2];
int n;
void get(int x,double s,double m)
{
    if(s<0 || s>c)
        return ;
    if(x==n+1)
    {
        ans=min(ans,m);
        return ;
    }
    for(int i=x;i<=n+1 && (cn[i][0]-cn[x][0])/d2<=c;i++)
        if((cn[i][0]-cn[x][0])/d2<=s)
            get(x+1,s-(cn[x+1][0]-cn[x][0])/d2,m);
        else
            get(x+1,(cn[i][0]-cn[x][0])/d2-(cn[x+1][0]-cn[x][0])/d2,m+((cn[i][0]-cn[x][0])/d2-s)*cn[x][1]);
    get(x+1,c-(cn[x+1][0]-cn[x][0])/d2,m+(c-s)*cn[x][1]);

}
int main()
{
    cin>>d1>>c>>d2>>p>>n;
    for(int i=1;i<=n;i++)
        cin>>cn[i][0]>>cn[i][1];
    cn[0][1]=p,cn[n+1][0]=d1;//初始化
    get(0,0,0);//从起点开始搜索
    if(ans==1e6)
        cout<<"No Solution";
    else
        printf("%.2lf",ans);
    return 0;
}