• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

Codeforces_448C分治

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

昨晚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\n",ans);
    }
    return 0;
}

  


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C#有没有什么办法可以判断DataGridView是否有行被选中发布时间:2022-07-14
下一篇:
C#中HTML字符转换函数发布时间:2022-07-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap