本文共 1510 字，大约阅读时间需要 5 分钟。

想象一下假如进行操作1,怎样是比较优秀的

$即为:对于[L,R]一段连续不为0的数字,设minn为其中最小的数字$

$怎样操作是最少的?$

$决策1:这段数字如果不进行操作1,那么答案是R-L+1$

$决策2:若进行操作1,至少进行minn次(否则没有一个元素变成0,无意义)$

$而且这minn次贪心的从L操作到R,元素的减少只会对后续更优$

$那么经过这minn次后,[L,R]分成若干个连续不为0的子段$

$我们发现这也是相同的子问题,对这些子段进行相同操作递归就好了$

所以最后,消除[L,R]就是在决策1和决策2中取小

#include 
   
    using namespace std;const int maxn=5009;int n,a[maxn];int dfs(int l,int r){	if( l==r )	return a[l]!=0;	int minn=1e9+1;	for(int i=l;i<=r;i++)		minn=min(minn,a[i]);//找到最小元素 	int last=0,ans=minn;	for(int i=l;i<=r;i++)	{		a[i]-=minn;//清空 		if( last==0&&a[i] )	last=i;		if( a[i]==0&&last )	ans+=dfs(last,i-1),last=0;//last到i-1就是连续不为0的子段 	}	if( a[r]!=0 )	ans+=dfs(last,r);	return min( ans,r-l+1 );//决策取小 }int main(){	cin >> n;	int last=0,ans=0;	for(int i=1;i<=n;i++)	cin >> a[i];	for(int i=1;i<=n;i++)	{		if( last==0&&a[i] )	last=i;		if( a[i]==0&&last )	ans+=dfs(last,i-1),last=0;	}	if( a[n]!=0 )		ans+=dfs(last,n);	cout << ans;}
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/108232140 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！