BFS

铺设道路

原题

利用差分数组解决

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

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