专栏文章

p1180 驾车旅游

CCrash_Man_CHN
P1180题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioipep0
此快照首次捕获于
2025/12/02 19:51
3 个月前
此快照最后确认于
2025/12/02 19:51
3 个月前
查看原文

前言

看到油箱，我以为是贪心，但题目中写了总是将油箱加满，所以不能用贪心了，唉，可恶

题目思路

暴搜

首先我们看到这道题目很明显，有两种情况：加油和不加油，也就是选或不选，想到这看到题目大小，不难想到可以用暴力搜索dfs，但这个算法的时间复杂度足足达到了O(2n2^n), 而n最大为50，2502^{50}肯定炸了……

剪枝

有一种优化方法叫剪枝，比如说举个例子：某xxs想买一台计算机，他的预算是500，而他正在看的计算机CPU+显卡的money就比500都要高了，那我们就没有必要继续去看这台计算机其他零件和主机的价格，直接看下一台，这就是剪枝，一个优化的东西

暴搜+剪枝

那么这道题目明确思路了: 暴搜+剪枝，那么我们要在哪里剪枝呢？不难想到若邮箱的油量大于一半，说明足以到达下一个加油站，所以不加油，那么这样就简单了秒变入门题，首先是判断能不能到加油站，有两种情况：1.不可以到，必须加油 2.可以到，若多于一半，则不选，反之搜索两种情况：(1)选 (2)不选 最后判断有没有到最后一个加油站，和加上剪枝即可

题目代码

CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
double dis,maxn,mile,start,half;
int n;
struct node
{
    double dis;
    double fare;
}a[N];
double ans;
void dfs(double oil,double cost,int cur)
{
    if(cost>ans)return ;
    if(cur==n+1)
    {
        ans=min(cost,ans);
        return ;
    }
    double z1=(a[cur+1].dis-a[cur].dis);
    double z2=z1/mile;
    if (oil*mile>=z1)
    {
        if (oil >= half)
        {
            dfs(oil-z2,cost,cur+1);
        }
        else
        {
            dfs(oil-z2,cost,cur+1);
            dfs(maxn-z2,cost+20+(maxn-oil)*a[cur].fare,cur+1);
        }
    }
    else dfs(maxn-z2,cost+20+(maxn-oil)*a[cur].fare,cur+1);
    return;
}
signed main()
{
    cin>>dis;
    cin>>maxn>>mile>>start;
    cin>>n;
    half=maxn/2;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i].dis>>a[i].fare;
        ans+=20+maxn*a[i].fare;
    }
    a[n+1]={dis,0.0};
    dfs(maxn-a[1].dis/mile,start,1);
    printf("%.1lf",ans);
    return 0;
}

后记

没想到不用剪枝也能过！！！！！！！！！！！！！！！！

NO!!!!!!!!!!!!!!!!!!!!!!!

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...