2019多校联讯 test 3 T2

曾经终败给现在 2021-12-23 23:57 154阅读 0赞

![1596060-20190609191922509-1700475750.png][]

![1596060-20190609191947477-1717671360.png][]

dfs+二分答案，二分可能的伤害值

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=1050;
    int n,m;
    int p[maxn][maxn];
    int dx[5]={
        0,1,-1,0,0};
    int dy[5]={
        0,0,0,-1,1};
    int l,r;
    bool flag;
    bool vis[maxn][maxn];
    void dfs(int x,int y,int cost)
    {
        if(x==n){
            flag=true;
            return;
        }
        for(int i=1;i<=4;i++)
        {
            int xx=x+dx[i];
            int yy=y+dy[i];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy]&&cost>=p[xx][yy])
            {
                vis[xx][yy]=true;
                dfs(xx,yy,cost);
            }
            if(flag==true) return;
        }
    }
    bool check(int x)
    {
        flag=false;
        memset(vis,0,sizeof(vis));
        dfs(1,1,x);
        if(flag) return true;
        else return false;
    }
    int main()
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%d",&p[i][j]);
            }
        }
        l=0,r=1000;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(check(mid)) r=mid-1;
            else l=mid+1;
        }
        printf("%d",l);
        return 0;
    }

转载于:https://www.cnblogs.com/LJB666/p/10994460.html

[1596060-20190609191922509-1700475750.png]: /images/20211223/30ad5ad8306b4b58831f2d86705c166a.png
[1596060-20190609191947477-1717671360.png]: /images/20211223/e750e4d7620b4655a8f539db4d915cd0.png

发表评论取消回复

表情：

评论列表（有 0 条评论，154人围观）

还没有评论，来说两句吧...

相关阅读

相关 2019牛客多校第10场

A：01概率退背包，这是赛后看题解补的，概率的背包和普通的背包有点不太一样，但思想还是差不多的 ![ContractedBlock.gif][] ![ExpandedBloc

Myth丶恋晨/ 2023年10月11日 09:16/ 0 赞/ 29 阅读

相关 2019 hdu多校1

A:一类线性dp，时间卡的有点紧 ![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] / 定义 dp[

悠悠/ 2023年10月11日 09:14/ 0 赞/ 33 阅读

相关 Studio 3T x64 2019.2.1版本Studio 3T下载激活

官方版本下载 2018.4.6版下载链接 2019.2.1版下载链接 CSDN下载 Studio 3T 使用教程 1.使用方法 2.试用指导：此脚本对20

妖狐艹你老母/ 2023年07月06日 14:50/ 0 赞/ 33 阅读

相关『NOIP 2019Day2 T3』保卫王国（defense）

重温NOIP2018的试题，发现只要好好想想还是能想出一些东西的。比如说本题是一个DDP的模板题，硬是做成了倍增优化DP的题目。 > 对于给出的$n$个节点的树，每个点都

我不是女神ヾ/ 2023年06月05日 11:27/ 0 赞/ 64 阅读

相关 2019.2.14 t3 车辆销售

![1597764-20190214210325079-854976076.png][]![1597764-20190214210333838-531980084.png][]

绝地灬酷狼/ 2022年01月09日 07:39/ 0 赞/ 193 阅读

相关 2019多校联讯 test 3 T2

![1596060-20190609191922509-1700475750.png][] ![1596060-20190609191947477-1717671360.pn

曾经终败给现在/ 2021年12月23日 23:57/ 0 赞/ 155 阅读

相关 2019.3.22 Week 12 : ZigBee and T/H chamber test

Test purposes Remove backside center ventilation holes, pls help to conduct climatic ch

叁歲伎倆/ 2021年12月23日 08:29/ 0 赞/ 168 阅读

相关 2019HDU多校第一场 1009 String

Problem Description Tom has a string containing only lowercase letters. He wants to cho

傷城~/ 2021年11月27日 00:44/ 0 赞/ 322 阅读

相关 Test 6.24 T2 集合

问题描述有一个可重集合,一开始只有一个元素 0。你可以进行若干轮操作,每轮你需要对集合中每个元素 x 执行以下三种操作之一: 1. 将 x 变为 x+1; 2

拼搏现实的明天。/ 2021年11月23日 15:52/ 0 赞/ 185 阅读

相关 2019佳木斯多校联训 Day1

　　　　T1 　　非常裸的大模拟,比较简单　　思路:用字符串存储数据,然后从后往前查找直到找到00,25,50,75中的任意一个,然后再用串长相减判断一下正反关系

红太狼/ 2021年10月24日 06:22/ 0 赞/ 233 阅读