【NOIP2013】Day2不完全题解+代码

T1

直接递归区间，从1-n开始，找到这个区间中的最小值然后将区间里的所有值都减去这个最小值

以被减去最小值之后的零点为分段分别递归处理即可。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;
int block[100003]={0},n=0;
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=1;i<=n;i++)scanf("%d",&block[i]);
    int ans=solve(1,n);
    printf("%d",ans);
    return 0;
}

int solve(int lf,int rt)
{
    if(lf>rt)return 0;
    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]==0)
        {
            tot+=solve(last,i-1);
            last=i+1;
            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[100003]={0},n=0;
int main(void)
{
    freopen("flower.in","r",stdin);
    freopen("flower.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&high[i]);
    int ans=1;
    bool check=false,check_2=false;
    if(high[2]>high[1])check=true;
    if(high[2]==high[1]&&high[3]>high[1])check=true;
    for(int i=2;i<=n;i++)
    {
        if(high[i]>high[i+1]&&check)
        {
            ans++;
            check=false;
            if(i==n)check_2=true;
            continue;
        }    
        if(high[i]<high[i+1]&&!check)
        {
            ans++;
            check=true;
            if(i==n)check_2=true;
            continue;
        }
    }
    if(!check_2)ans++;
    printf("%d",ans);
    return 0;
}

T3

我没写……但是应该就是搜搜搜……

不会写搜索的蒟蒻】