#include <iostream> using namespace std; const int N = 100010; int p[N];//要去的城市 int A[N], B[N], C[N]; long long s, ans[N];//ans差分数组 int main() { int N, M; scanf("%d%d", &N, &M); for(int i = 1; i <= M; i ++ )//要去的城市 { scanf("%d", &p[i]); } // 输入每段路的Ai Bi Ci 有N - 1段路 for(int i = 1; i <= N - 1; i ++ ) scanf("%d%d%d", &A[i], &B[i], &C[i]); for(int i = 1; i <= M - 1; i ++ )//要去M个城市,相邻城市间有一小段路,因此经过M - 1 { //用差分保存经过的次数 ans[min(p[i], p[i + 1])] ++;//让前面的++ 后面的-- ans[max(p[i], p[i + 1])] --; } //求他的前缀和然后再全部赋值给他这个差分数组 此时该数组存的就是经过次数 for(int i = 1; i <= N; i ++ ) ans[i] += ans[i - 1]; //N-1段路 看看哪个方案比较省钱 算一下最min花钱的并存入s for(int i = 1; i <= N - 1; i ++ ) s += min(A[i] * ans[i], (B[i] * ans[i] + C[i])); printf("%lld", s); return 0; }
标签:洛谷,int,高铁,long,ans,3406 From: https://www.cnblogs.com/FISH-Q/p/17438446.html