/ OIer TK / 题库 /

佳佳的魔法阵

佳佳的魔法阵

测试数据来自 system/1284

背景

也许是为了捕捉猎物(捕捉MM?),也许是因为其它原因,总之,佳佳准备设计一个魔法阵。而设计魔法阵涉及到的最关键问题,似乎就是那些带有魔力的宝石的摆放……

描述

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

样例输入1

2 2 2 2

样例输出1

4

限制

1秒

来源

wxsxg

信息

ID
1263
难度
(无)
分类
搜索 | 搜索与剪枝 点击显示
标签
递交数
0
已通过
0
通过率
?
上传者