解题报告 P3406 海底高铁

题目内容

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);
}