Painting fence
题意
乍一看以为是之前做过的一道单调队列优化的DP,不是。
也是有n块木板,每个木板宽1米,有一个高度ai,现在要把他们刷成橘色,给了你一个宽一米的刷子,你可以横着刷,或者竖着刷,问最少需要刷几下才能将所有的木板着色。
思路
对于一个区间[l,r]的木板来说,第一步要么把所有的木板都竖着刷,要么把最低的木板横着刷一遍,问题变为区间所有的木板减去最短木板的高度之后,刷分为的两个小区间的次数和+最短木板高度。两者取最小值即可。分治
代码
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=1e5+10;
const int mod=1e9+7;
const ll inf=0x3f3f3f3f3f3f3f3f;
const double eps=1e-14;
int arr[N];
int solve(int l,int r)
{
if(l>r) return 0;
int pos,minn=inf;
for(int i=l;i<=r;i++)
{
if(arr[i]<minn)
{
minn=arr[i];
pos=i;
}
}
for(int i=l;i<=r;i++) arr[i]-=minn;
return min(r-l+1,solve(l,pos-1)+solve(pos+1,r)+minn);
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&arr[i]);
printf("%d\n",solve(1,n));
return 0;
}
原文链接: https://www.cnblogs.com/valk3/p/12765660.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/344202
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!