Codeforces_448C 分治

昨晚CF碰到的题目,昨晚CF跪了啊啊啊

题意比较简单,给定一排挨在一起的板子,宽度都为1,高度不一,一个刷子宽度也是1,可以横着刷,也可以竖着刷,但是任何时刻刷子都要在板子上,也就是说,如果横向的时候,出现断层,就要算2次或者多次了 最后求全部刷完的最小刷的次数

昨晚真的是想了各种方法,dp也想了,二分结果也想了,主要是他这个到了高处,互相不连通的时候,也不好怎么搞。

好吧,进入正题,最后是用分治解决,也有说是dp的,其实也可以说是dp,毕竟分治本身也是种dp思想,我大dp果然是无穷无尽。

这个分治有点像区间dp,先从这个区间开始,最大值肯定是 r-l+1不,然后找到最矮的板子,就把他横向刷掉,然后往该板的两边继续递归,每次比较 竖向刷最大值 和 横向刷最矮板子中最小的,因为每次都是刷最小的,所以不会出现断层的现象,而且横向要么就不刷,刷的话肯定至少把最小的要刷掉,如果连最小的都没刷掉,不是白刷了。

板子最多只有5000块,因此每次至少刷掉了一块板子,所以整个dfs不会超过5000次。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int A[5010];
int n;
int solve(int l,int r,int h)
{
    if (l>r) return 0;
    int loc=-1,mini=1<<30;
    int sum=0;
    for (int i=l;i<=r;i++){
        if (mini>A[i])
        {
            mini=A[i];
            loc=i;
        }
            if (A[i]>h) sum++;
    }
    //if (loc==-1) return 0;
    int tmp=A[loc]-h; //即使当前最小板子已经被刷过了,也要继续递归下去,因为还可能有其他板子没刷到,h代表当前已经刷到的高度。
    if (tmp<0) tmp=0;
    return min(sum,solve(l,loc-1,max(A[loc],h))+solve(loc+1,r,max(A[loc],h))+tmp);
}
int main()
{
   // cout<< (1<<30)<<endl;
    while (scanf("%d",&n)!=EOF)
    {
        for (int i=1;i<=n;i++) scanf("%d",&A[i]);
        int ans=solve(1,n,0);
        printf("%d
",ans);
    }
    return 0;
}

  

原文地址:https://www.cnblogs.com/kkrisen/p/3854337.html