【解题报告】洛谷P3406 海底高铁

题目链接

https://www.luogu.com.cn/problem/P3406

思路

先统计一下每段铁路连接的两所城市各自被访问了多少次，然后做一个前缀和，表示一段铁路要走多少次

然后我们贪心地选择是选择买票还是选择买ID

这样的营销套路就像万恶的并夕夕

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
long long n,m;
long long p[100005];
long long v[100005]={0};
long long ans;
int main()
{
	std::ios::sync_with_stdio;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	cin>>p[i]; 
	for(int i=1;i<m;i++)
	{
		int x=max(p[i],p[i+1]);
		int y=min(p[i],p[i+1]);
		v[y]++;
		v[x]--;
	}
	for(int i=1;i<=n;i++)
	v[i]+=v[i-1];
	for(int i=1;i<n;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		ans+=min(a*v[i],b*v[i]+c);
	}
	cout<<ans<<'\n';
	return 0;
}