P5019 [NOIP2018 提高组] 铺设道路
查看原帖
P5019 [NOIP2018 提高组] 铺设道路
448474
ximena楼主2021/6/2 19:10

一直是30分 不知道怎么改

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define speed(x) ios::sync_with_stdio(false), cin.tie(x), cout.tie(x)
#define bug(x) cout << #x << " == " << x << '\n';
#define ll long long
const ll int MAX_N = 2e5 + 5;
int a[MAX_N]={0};
int sum=0;
int n;
void solve(int l,int r)
{
    if(l<1||r>n)return ;
    if(l>r)return ;
    int minn=INF,index1=0;

    for(int i=l;i<=r;i++)
    {
       if(minn>a[i])
       {
           minn=a[i];
           index1=i;
       }
    }

    if(minn>0)
    {
        int index2=index1;
        for(int i=l;i<=r;i++)
        {
            a[i]-=minn;
            if(a[i]==0)
            {
                index2=i;
            }
        }
        sum+=minn;
        if(index1>l)
        solve(l,index1-1);
        if(index2<r)
        solve(index2+1,r);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    solve(1,n);
    printf("%d\n",sum);
}

2021/6/2 19:10
加载中...