P1585 魔法阵

    • 133通过
    • 585提交
  • 题目提供者 JOHNKRAM
  • 评测方式 云端评测
  • 标签 剪枝 搜索 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    魔法阵是一个n×m的格子(高n,宽m),n×m为偶数。Smart手中有n×m个宝石(以1~n×m编号)。Smart从最右上角的格子开始走,从一个格子可以走到上、下、左、右4个相邻的格子,但不能走出边界。每个格子必须且仅能到过1次,这样Smart一共走了n×m个格子停止(随便停哪里)。Smart每进入一个格子,就在该格子里放入一颗宝石。他是按顺序放的,也就是说——第i个进入的格子放入i号宝石。

       如果两颗宝石的编号对n×m÷2取模的值相同,则认为这两颗宝石相互之间有微妙的影响。也就是说,我们按照宝石的编号对n×m÷2取模的值,将宝石分成n×m÷2对,其中每对都恰有两颗宝石。对于每一对宝石,设第一颗宝石在第a行第b列,另一颗宝石在第c行第d列,那么定义这2个宝石的魔力影响值为 k1×|a-c|+k2×|b-d|。 需要你求出的是,在所有合乎题意的宝石摆放方案中,所有成对的宝石间的最大魔力影响值的最小值为多少。换句话说,如果我们定义对n×m÷2取模的值为i的一对宝石的魔力影响值为a[i]。你需要求出的就是max{a[i]|i=0,1,2...}的最小值。

    输入输出格式

    输入格式:

    只有一行用空格隔开的4个整数,分别是n、m、k1、k2。(n×m≤50,0<k1,k2≤32767)

    输出格式:

    只需输出一个整数,即题目所要求的“所有成对的宝石间的最大魔力影响值的最小值”。

    输入输出样例

    输入样例#1: 复制
    2 2 2 2
    输出样例#1: 复制
    4
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。