有两种操作：1，区间整体减去1，需要整体大于1。2，一个数减去任意值。问最少几次使区间归零； 首先，如果操作1，一定是减去区间最小值，否则没有意义，操作2也一定是减到0，先2后1可以等效成先1最后2； 对整个区间暴力递归就可以； 每次递归的时候区间减去最小值，不管选哪个这部分都会减去，不减会对后面造成干扰；
#include <iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<queue> #define pb push_back #define fi first #define se second #define sz(x) x.size() #define cl(x) x.clear() #define all(x) x.begin() , x.end() #define rep(i , x , n) for(ll i = x ; i <= n ; i ++) #define per(i , n , x) for(int i = n ; i >= x ; i --) #define mem(x) memset(x , 0 , sizeof(x)) #define mem_1(x) memset(x , -1 , sizeof(x)) #define mem_inf(x) memset(x , 0x3f3f3f3f , sizeof(x)) #define debug(x) cout << '*' << x << '\n' #define ddebug(x , y) cout << '*' << x << ' ' << y << '\n' using namespace std ; typedef long long ll ; typedef pair<int , int> pii ; typedef pair<ll , ll> pll ; const ll mod = 1e9+7; const ll maxn = 1e6 + 10 ; const int inf = 0x3f3f3f3f ; int n,m,a[maxn]; int so(int l,int r) { if(l>r)return 0; int mi=l,cnt=0,tm; rep(i,l,r) { if(a[i]<a[mi])mi=i;//找最小值 if(a[i])cnt++;//不为0的个数 } tm=a[mi]; rep(i,l,r)a[i]-=tm; return min(cnt,tm + so(l,mi-1) + so(mi+1,r)); } int main() { cin>>n; rep(i,1,n) cin>>a[i]; cout<<so(1,n); }