E. Clear the Multiset
题意
给出一个数组a,长度为n<5000
对于一次操作有两种选择：
1.使a[L~R]-1
2.使a[i]-x
问最少几次操作得到全为0的数组
题解
对于一个局面，我们的操作顺序并不影响最终的答案
对于一个区间[L,R] 将其中的数全变为0,
要么只使用操作2,将L到R内的数逐个归0,共R-L+1次操作
要么找到区间内最小值minn,它在位置mpos
使用操作1将区间[L,R]都减去minn,递归求解[L,mpos-1]和[mpos+1,R]区间的子问题
则对于区间[L,R]的最小操作次数:
1
| ans=min(minn+divid_conquer(L,mpos-1,minn)+divid_conquer(mpos+1,R,minn)-Min,R-L+1)
|
其中Min为上个区间中的最小值,即[L,R]的区间最小值记为Min
[L,mpos-1]的区间最小值为minn，且minn>=Min一定成立
对于递归边界当(L==R)是若data[L]-Min!=0则使用1次操作2 否则返回0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=5000+5;
const double Pi=acos(-1);
const ll Mod=1e9+7;
int data[Max];
ll divid_conquer(ll L,ll R,ll Min){
if(L==R)return (data[L]-Min>0?1:0);
else if(L>R)return 0;
int minn=1e9+5,mpos=0;
for(int i=L;i<=R;i++){
if(minn>data[i]){
minn=data[i];
mpos=i;
}
}
ll ans=min(minn+divid_conquer(L,mpos-1,minn)+divid_conquer(mpos+1,R,minn)-Min,R-L+1);
return ans;
}
int main() {
Turnoff;
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>data[i];
ll ans=divid_conquer(1,n,0);
cout<<ans<<endl;
}
|