P2200 炉石collection

    • 2通过
    • 31提交
  • 题目提供者 LittleZ
  • 评测方式 云端评测
  • 标签 高性能
  • 难度 尚无评定
  • 时空限制 400ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    小Z最近沉迷于一个叫做炉石 collection 的游戏。在游戏中,你需要使用排在 N × N 的矩阵内的卡牌来击败你的敌人。

    在这个游戏中,排兵布阵是游戏的一个重要内容,例如“日怒保卫者”和“上古看守者”放在一起可以起到更好的效果。为了游戏的平衡性,同样种类的卡牌最多只能出战 2 张。

    在一次激烈的战斗之后,小Z想要重新编排他的队伍。在游戏中,小Z可以支付 A 枚金币让你任意横向交换卡牌,支付 B 枚金币让你任意纵向交换卡牌。

    你只需要支付一次金币就可以进行某种类型的交换任意次,直到你停下并进行另一种类型的交换,此时需要支付另一种类型交换的费用。例如,横向交换 -横向交换 -纵向交换 -纵向交换 -纵向交换 -横向

    交换 -纵向交换总共要支付 2A + 2B 枚金币。

    小Z想要知道,他最少要支付多少金币把他目前的布置变换成他想要的布置。

    输入输出格式

    输入格式:

    第一行包含三个数字 N 、A、B,分别表示矩阵的大小,横向交换的费用,纵向交换的费用。

    接下来 N 行每行包含 N 个整数,表示开始交换前矩阵内每个位置卡牌的类型。

    接下来 N 行每行包含 N 个整数,表示目标矩阵内每个位置卡牌的类型。

    输出格式:

    输出最少需要支付多少金币能够把目前的布置变换成他想要的布置。如果不能变换成功,输出“Fail”(不包含引号)。

    输入输出样例

    输入样例#1: 复制
    3 16 9
    2 5 6
    1 1 3
    7 8 3
    2 5 1
    3 3 6
    7 8 1
    输出样例#1: 复制
    34
    输入样例#2: 复制
    2 193 43
    1 2
    2 1
    1 2
    2 3
    输出样例#2: 复制
    Fail
    输入样例#3: 复制
    3 10 20
    1 2 3
    4 5 4
    3 2 1
    2 1 2
    1 5 3
    4 3 4
    输出样例#3: 复制
    30

    说明

    【数据规模】

    对于 68% 的数据,答案最多只需要支付 1 次费用。

    对于 86% 的数据,答案最多只需要支付 2 次费用。

    对于 100% 的数据,1 ≤ n ≤ 300; 1 ≤ A,B ≤ 1000000; 1 ≤ 卡牌类型的标号 ≤ 100000。

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