Wannafly模拟赛5 E

阅读: 评论:0

Wannafly模拟赛5 E

Wannafly模拟赛5 E

题目描述

????接到了一份来自校方的委托,虽然没有学分但也必须完成。
需要粉刷?条木板,这些木板按照左端对齐,每条木板的高度都是1,
第?条木板的长度为??。
????只有一个宽度为1的刷子,她每次可以水平或者竖直地对连续的
位置进行粉刷,刷子不能经过没有木板的位置。
????对校方的这个安排非常不满,但为了效率,她允许重复粉刷一个
位置,希望通过最少的次数来完成这?条木板的粉刷。

输入描述:

第一行,一个正整数?。
第二行,?个正整数??。

输出描述:

一行,一个整数,需要进行的最小粉刷次数。
示例1

输入

5
2 2 1 2 1

输出

3

备注:

对于20%的数据,?,?? ≤ 5。
对于50%的数据,?,?? ≤ 200。
对于70%的数据,?? ≤ 3000。
对于100%的数据,? ≤ 3000,?? ≤ 109。

思路:分治,刷n行油漆,一行一行刷需要n次,
假设最小行高度为t, 如果t>=n,那么最少需要刷
n次,全都竖着刷,如果t<n, 那么可以先横着刷t
次,然后把n个木板分成了若干个连续的部分,然后和刷
n块木板类似,然后比较 t+刷剩下的最小的步数和n比较
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<queue>
#include<map>using namespace std;int mix=1e9+7;int n,ans,a[3300];int dfs(int c[3300],int n1,int mi)
{int d[3300],t=0,mi1=mix,s=0;for(int i=0;i<n1;i++){if(c[i]-mi>0){d[t++]=c[i]-mi;if(d[t-1]<mi1)mi1=d[t-1];}else if(t!=0){if(mi1<t){d[t]=0;s=s+min(t,dfs(d,t+1,mi1));if(s+mi>=n1-1)break;}else{s=s+t;if(s+mi>=n1-1)break;}t=0;mi1=mix;}}if(n1-1<s+mi)return n1-1;return s+mi;
}int main()
{scanf("%d",&n);ans=n;int mi=n;for(int i=0;i<n;i++){scanf("%d",&a[i]);if(mi>a[i]&&a[i]!=0)mi=a[i];if(a[i]<=0)ans--;}int s=n;if(mi<ans){s=0;a[n]=0;//最后加个0标记ans=min(ans,dfs(a,n+1,mi));}printf("%d",ans);return 0;
}

 

转载于:.html

本文发布于:2024-01-28 07:07:36,感谢您对本站的认可!

本文链接:https://www.4u4v.net/it/17063968625676.html

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

标签:Wannafly
留言与评论(共有 0 条评论)
   
验证码:

Copyright ©2019-2022 Comsenz Inc.Powered by ©

网站地图1 网站地图2 网站地图3 网站地图4 网站地图5 网站地图6 网站地图7 网站地图8 网站地图9 网站地图10 网站地图11 网站地图12 网站地图13 网站地图14 网站地图15 网站地图16 网站地图17 网站地图18 网站地图19 网站地图20 网站地图21 网站地图22/a> 网站地图23