死路:

大暴力帝国之超强枚举，时间复杂度应该是O(n²)

代码（可不看）：

#include <bits/stdc++.h>
using namespace std;
int n,m,lastp,p,a,b,c,sum[100005]={},ans=0;
int main(){
	cin>>n>>m>>lastp;
	for(int i=1;i<m;i++){
		scanf("%d",&p);
		if(p>lastp)for(int j=lastp;j<p;++j)sum[j]++;
		else for(int j=p;j<lastp;j++)sum[j]++;
		lastp=p;
	}
	for(int i=1;i<n;i++){
		scanf("%d%d%d",&a,&b,&c);
		ans+=min(sum[i]*a,sum[i]*b+c);
	}
	printf("%d",ans);
	return 0;
}

是Time Limit Exceeded，我们有救了！！！

一看，题目数据范围：

M,N≤10⁵

显然是会 Time Limit Exceeded 的

思路：

我们令cnt[i]=a[i]-a[i-1]

有：

a[i]=cnt[i]+a[i-1]

=cnt[i]+cnt[i-1]+cnt[i-2]+a[i-3]

……

=cnt[i]+cnt[i-1]+cnt[i-2]+……+cnt[1]

我们发现，若给cnt[i]+x：

则：

a[i],a[i+1],a[i+2],……都加了x

所以要给a[x]到a[y]都加z分，

只要cnt[x]+=z,cnt[y+1]-=z，

最后再用数组cnt就是修改后的经过次数、

for(int i=1;i<n;i++)cnt[i]+=cnt[i-1]+cnt[i];

现在cnt就是修改后的经过次数

这就是差分！！！

AC代码：

#include<bits/stdc++.h>
using namespace std;
long long n,m,p[100005],a[100005],b[100005],c[100005],cnt[100005],ans=0;
int main() {
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>p[i];
	}
	for(int i=1;i<n;i++){
		cin>>a[i]>>b[i]>>c[i];
	}
	for(int i=1;i<m;i++){//差分
		int l=min(p[i],p[i+1]);
		int r=max(p[i],p[i+1]);
		cnt[l]++;
		cnt[r]--;
	}
	for(int i=1;i<n;i++){//反推，计算每个城市经过次数
		cnt[i]+=cnt[i-1];
	}
	for(int i=1;i<n;i++){
		int p_true=cnt[i]*a[i];//不买卡
		int p_false=cnt[i]*b[i]+c[i];//买卡
		ans+=min(p_true,p_false);
	}
	cout<<ans;
	return 0;
}

I love 压行！！

#include<bits/stdc++.h>
using namespace std;
long long n,m,p[100005],a[100005],b[100005],c[100005],cnt[100005],ans=0;
int main() {
	cin>>n>>m;
	for(int i=1;i<=m;i++)cin>>p[i];
	for(int i=1;i<n;i++)cin>>a[i]>>b[i]>>c[i];
	for(int i=1;i<m;i++)cnt[min(p[i],p[i+1])]++,cnt[max(p[i],p[i+1])]--;
	for(int i=1;i<n;i++)cnt[i]+=cnt[i-1];
	for(int i=1;i<n;i++)ans+=min(cnt[i]*a[i],cnt[i]*b[i]+c[i]);
	cout<<ans;
	return 0;
}

求赞

知道我敲字有多累吗

老规矩，先点赞再看

思路：先用差分计算每个城市所经过的次数，再判断是否值回卡价

#include<iostream>
using namespace std;
long long n,m,sum,a[100100],b[100100],u[100100],f[100100],ep[100100],cha[100100]; 
int main(){
	cin>>n>>m>>a[1];
	for(int i=2;i<=m;i++){
		cin>>a[i];
		cha[max(a[i],a[i-1])]--;//差分两端分别--，++
		cha[min(a[i],a[i-1])]++;
	}
	for(int i=1;i<n;i++)b[i]=b[i-1]+cha[i];//计算每个城市经过次数
	for(int i=1;i<n;i++){
		cin>>u[i]>>f[i]>>ep[i];
		if(b[i]*(u[i]-f[i])>ep[i])u[i]=f[i],sum+=ep[i];//判断是否能值回卡价，如果能，就买卡
	}
	for(int i=1;i<n;i++)sum+=b[i]*u[i];//计算总价
	cout<<sum;
	return 0;
}

点踩被我发现就完了

是谁点的踩！