中文题 简单搜索题

例数据

输入 6

1 1 1 1 9 9

输出 3

注意是每一个递归搜索都返回一个min 而不是只有总的返回min

#include 
     
      #include 
      
       #include 
       
        using namespace std;int a[5678];int dfs(int l,int r,int k){    if(l>r||(l==r&&a[l]<=k)) return 0;    if(l==r) return 1;    //注意区间左闭右开 只有这里r+1考虑右边界    int mn=min_element(a+l,a+r+1)-a;    //注意-k    return min(r-l+1,dfs(l,mn-1,a[mn])+dfs(mn+1,r,a[mn])+a[mn]-k);}int main(){    int n;    while(scanf("%d",&n)!=EOF)    {        memset(a,0,sizeof(a));        for(int i=0;i
       
      
     

 

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;int n,a[100005];int get(int l,int r){    int minn=1e9+3;    for(int i=l;i<=r;i++)    {        minn=min(minn,a[i]);    }    int ans=minn;    for(int i=l;i<=r;i++)    {        if(a[i]==minn)            continue;        int ii=i+1;        while(ii<=r&&a[ii]!=minn)            ii++;        ii--;        for(int j=i;j<=ii;j++)            a[j]-=minn;        ans+=get(i,ii);        i=ii;    }    return min(r-l+1,ans);}int main(){    //freopen("in.txt", "r", stdin);    while(~scanf("%d",&n))    {        for(int i=0;i