CF1400E. Clear the Multiset（分治，递归）

题目链接：https://codeforces.ml/contest/1400/problem/E

描述：

给出序列a,有两种操作：

1.将区间[l,r]的数减一。

2.将a[x]变为0.

求将a全变为0最少的操作步数。n<=5000,0<=a[i]<=1e9;

分析：

区间由0被分为若干个小区间，每个区间若经过x次操作一后，无法消去>=x个数，则说明操作二更优。所以可以分治，对一个区间，找出最小值min，然后进行min次操作一，将区间分为若干小区间，然后再解决小区间。每个区间的答案与r-l+1（只用操作二）取较小值

#include<bits/stdc++.h> #define N 5010 #define ll long long using namespace std; int n,a[N]; int dfs(int l,int r){//cout<<l<<" "<<r<<endl; if(l>r)return 0; if(r==l){ if(a[l])return 1; return 0; } int mn=2e9,ret=r-l+1; for(int i=l;i<=r;i++)mn=min(mn,a[i]); for(int i=l;i<=r;i++)a[i]-=mn; int t=l,tot=mn; for(int i=l;i<=r;i++){ if(a[i]==0){ tot+=dfs(t,i-1);t=i+1; } } if(a[r])tot+=dfs(t,r); return min(tot,ret); } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); printf("%d",dfs(1,n)); return 0; }