T1
直接递归区间，从1-n开始，找到这个区间中的最小值然后将区间里的所有值都减去这个最小值
以被减去最小值之后的零点为分段分别递归处理即可。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;
int block[]={},n=;
int solve(int lf,int rt);
int main(void)
{
freopen("block.in","r",stdin);
freopen("block.out","w",stdout);
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d",&block[i]);
int ans=solve(,n);
printf("%d",ans);
return ;
} int solve(int lf,int rt)
{
if(lf>rt)return ;
if(lf==rt)return block[lf];
int least=0x7fffffff;
for(int i=lf;i<=rt;i++)least=min(least,block[i]);
int tot=least,last=lf;
for(int i=lf;i<=rt;i++)
{
block[i]-=least;
if(block[i]==)
{
tot+=solve(last,i-);
last=i+;
continue;
}
if(i==rt)tot+=solve(last,rt);
}
return tot;
}
T2
常规解法是DP然后使用树状数组\线段树来加快状态转移速度
但是这道题有一个结论
对于花组成的区间，我们可以视作是单调性不同的单调区间拼成的（忽视掉相等的情况），那么在每一个单调区间之中
很明显选择区间的两个端点是最优选择，那么我们的最优解就是选出所有区间的端点。也即是折点。
这样就可以O（n）解决。
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
int high[]={},n=;
int main(void)
{
freopen("flower.in","r",stdin);
freopen("flower.out","w",stdout);
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d",&high[i]);
int ans=;
bool check=false,check_2=false;
if(high[]>high[])check=true;
if(high[]==high[]&&high[]>high[])check=true;
for(int i=;i<=n;i++)
{
if(high[i]>high[i+]&&check)
{
ans++;
check=false;
if(i==n)check_2=true;
continue;
}
if(high[i]<high[i+]&&!check)
{
ans++;
check=true;
if(i==n)check_2=true;
continue;
}
}
if(!check_2)ans++;
printf("%d",ans);
return ;
}
T3
我没写……但是应该就是搜搜搜……
不会写搜索的蒟蒻】