题目内容

P3406

大意:一个高铁,每段路有票和IC卡两种选择,问最少费用

解题思路

嗯,这题的思路不太好想,看似dp实际上不是。要求最小费用,就涉及到买卡还是买票的决策。而买票还是买卡取决于通过这段铁路的次数。又由于主人公是在各个城市间到处晃,所以可以开一个差分数组记录每段铁路通过的次数。

使用差分数组时,相当于区间加,然后确定铁路的通过次数后就可以计算是买卡省钱还是买票省钱。时间复杂度O(n),看似常数较大,但是实际跑得飞快,不开读优不吸氧可以155ms)

细节:
– 要开long long,不然会炸(最坏情况1e6*1e6会爆int)
– 由于i铁路连接i和i+1,所以在差分时右端点不用加1

代码:

#include <cstdio>
#include <algorithm>
typedef long long ll;
using namespace std;

const int maxn=1e5+5;
int n,m;
ll p[maxn],a[maxn],b[maxn],c[maxn];
ll time[maxn];//每条铁路乘坐次数的差分数组
//i铁路连接i和i+1

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%lld",&p[i]);
    for(int i=1;i<n;i++)
        scanf("%lld %lld %lld",&a[i],&b[i],&c[i]);
    for(int i=1;i<m;i++)
    {
        int l=min(p[i],p[i+1]),r=max(p[i],p[i+1]);//注意判断l和r的大小
        time[l]++,time[r]--;//由于i铁路连接i和i+1,所以r不要加一
    }
    ll ans=0;
    for(int i=1;i<=n;i++)//进入决策环节
    {
        time[i]+=time[i-1];//把差分加上来获取源数据
        if(a[i]*time[i]>c[i]+b[i]*time[i])//做比较
            ans+=c[i]+b[i]*time[i];
        else
            ans+=a[i]*time[i];
    }
    printf("%lld\n",ans);
}
最后修改日期:2020年2月7日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。