P2238 逛庙会

    • 50通过
    • 152提交
  • 题目提供者 kkksc03 吉祥物
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 状态压缩,状压 O2优化 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    本题时限3s,请考虑常数优化或者读入优化。(std没有特别进行优化)

    题目描述

    城市里正在举行庙会。庙会里有很多摊位。庙会的会场是一个南北向H个摊位、东西向W个摊位组成的大型方阵。从北开始第i行、西开始第j列的一个摊位,我们表示为(i,j)。

    正妹现在处于庙会的(1,1)位置,然后要往东或者往南走,一直走到(H,W)跟八尾勇汇合。(1,1)点和(H,W)和它们的东西南北邻近一个摊位都没有开张。别的地方也可能有一些摊位没有开张。

    正妹是个吃货。只要到达一个摊位,总是经不起小吃的诱惑。如果这个摊位开张了,而且该摊位小吃还没有买过,就会买下这个摊位的小吃。无论这个摊位是否有开张,其东西南北直接相邻的摊位小吃的香味也很诱人,如果邻近的摊位的小吃没有买过,那么就在这些邻近(上下左右)的且没有买过的摊位(假设有r个)中,买其中的r-1个摊位的小吃。然后继续往东或者南走。同一家小摊,不会购买多次。

    虽然正妹是个吃货,但是零用钱还是很有限。可是她又是管不住自己,就是要买买买。所以她希望知道自己最少能吃掉多少钱的东西。

    输入输出格式

    输入格式:

    第一行2个数,H,W

    接下来H行,每行W个字符串,没有空格隔开,是1-9或者'.'中的一个,表示价格,一个点表示没有开张。

    输出格式:

    一个整数,表示最少花掉的钱

    输入输出样例

    输入样例#1: 复制
    5 5
    ....7
    .21.8
    9346.
    ..45.
    .8...
    输出样例#1: 复制
    9

    说明

    样例解释:o为正妹经过的路线,x为她顺便买的小吃。当走到(2,4)时,左下右都有开张且没有买过的摊位,于是买左和右,继续沿着路线走。由于之后路线没有经过没有买过摊位,而且上下左右开张且没买过的摊位不超过1,所以一个都不买了。
    5 5
    oooo7
    .2xoo
    9346o
    ..45o
    .8..o

    20%数据,开张的摊位不超过20

    100%数据, (3 ≦ H ≦ 1000, 3 ≦ W ≦ 1000)

    特别注意:数据是在windows生成,输入数据换行符可能是“\r\n”(两个字符)或者"\n"。而评测机是linux。请特别注意。不接受赛后以“本地能过,评测wa”的理由申诉。

    参考读入方式(节选自std):

        for (i = 0; i < H; ++i) {
            scanf("%s", in);
            for (j = 0; j < W; ++j) {
                shop[i][j] = blabla..
            }
        }
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。