0%

BFS

铺设道路

原题

利用差分数组解决

直接画图就可以发现,连续的,一个层次的道路可以同时解决,不需要额外成本.直接求出所有”层次”的第一个位置即可,即为差分中正的项.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+4;
int a[maxn];
int d[maxn];
int main()
{
int n;cin>>n;
a[0]=0;
for(int i=1;i<=n;++i)cin>>a[i],d[i]=a[i]-a[i-1];
long long ans=0;
for(int i=1;i<=n;++i)if(d[i]>0)ans+=d[i];
cout<<ans<<endl;
return 0;
}