c++编程问题花园浇水

花园浇水
难度:黄金◎时间限制:1秒 占用内存:128M
小码哥需要给花园浇水。花园是1xn的长方形。每块地有一个高度。他会选择一块地方浇水，如果与这块地相邻的区域的高度小于等于这块地的高度，水就可以流过去，直到不能流为止。求他一次最多可以浇灌多少块地。
格式
输入格式:第一行为一个正整数n,
第二行为初始高度。
输出格式:输出一-行一个整数表示答案。

我的思路：建立数组a[n]存储每块地的高度；建立h[n]记录选第n块地浇水，最多浇灌多少块地；
依次比较a[n]中各项，求出h[n]，输出h[n]中最大值hmax。

预计效果：
输入：8
1 2 1 1 1 3 3 4
输出：6

参考题解如下：

该回答引用ChatGPT
下面是一种可行的解法：

1、从左往右遍历整个长方形，找到第一个最低的地块作为浇水的开始。

2、从该地块向两边扩展，并判断是否能流动。如果能，则扩展到最远的地方。

3、求出当前的浇水面积。

4、对剩下的区域重复以上步骤，找到下一个最低的地块，并计算其可浇水的面积。

5、最后累加所有浇水面积，即为最终答案。

以下是C++代码实现：

#include <iostream>
#include <vector>

using namespace std;

const int N = 10010;

int n;
int h[N];

int solve(int l, int r) {
    int minh = h[l];
    for (int i = l; i <= r; i++) {
        minh = min(minh, h[i]);
    }
    int res = minh * (r - l + 1);
    int last = l;
    for (int i = l; i <= r; i++) {
        if (h[i] == minh) {
            res = max(res, solve(last, i - 1));
            last = i + 1;
        }
    }
    res = max(res, solve(last, r));
    return res;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }
    cout << solve(0, n - 1) << endl;
    return 0;
}

以下是一种 C++ 实现的解决方案：

#include<bits/stdc++.h>
using namespace std;

const int N=10010;
int a[N];

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int ans=0;
    for(int i=0;i<n;i++)
    {
        int l=i,r=i,cnt=1;
        while(l-1>=0&&a[l-1]>=a[i])
        {
            l--;
            cnt++;
        }
        while(r+1<n&&a[r+1]>=a[i])
        {
            r++;
            cnt++;
        }
        ans=max(ans,cnt);
    }
    cout<<ans<<endl;
    return 0;
}

该代码使用两个指针，从当前位置向左和向右扩展，并计算**
能覆盖的地块数。最终比较所有地块覆盖的数量，选出最大的一个作为结果。

• 这个问题的回答你可以参考下: https://ask.csdn.net/questions/7782285

#include<iostream>
#include<cstring>
using namespace std;
const int N=100010;
int h[N],f[N];
int n;
int dfs(int u){
    int res=0;
    if(f[u]) return f[u];
    int l=u-1,r=u+1;
    while(h[l]<=h[u]&&l>=1) l--;
    while(h[r]<=h[u]&&r<=n) r++;
    res=r-l-1;
    f[u]=max(f[u],dfs(l)+res);
    f[u]=max(f[u],dfs(r)+res);
    return f[u];
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>h[i];
    cout<<dfs(1)<<endl;
    return 0;
}