|
|
|
|
背景 Background |
|
|
|
也许是为了捕捉猎物（捕捉MM？），也许是因为其它原因，总之，佳佳准备设计一个魔法阵。而设计魔法阵涉及到的最关键问题，似乎就是那些带有魔力的宝石的摆放……
|
|
|
|
|
|
|
|
描述 Description |
|
|
|
魔法阵是一个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...}的最小值。
|
|
|
|
|
|
|
|
输入格式 Input Format |
|
| |
只有一行用空格隔开的4个整数，分别是n、m、k1、k2，n*m<=50，0<k1,k2<=32767。
|
|
|
|
|
|
|
|
输出格式 Output Format |
|
| |
只需输出一个整数，即题目所要求的“所有成对的宝石间的最大魔力影响值的最小值”。 |
|
|
|
|
|
|
|
|
Flag |
|
题号 |
P1284 |
|
其它 |
通过 |
0人 |
提交 |
0次 |
通过率 |
0% |
难度 |
3 |
|
|
|
|
|
|
