建模思想的一点点应用(另:打表大法好!)

作者: shad0w_walker(admin) 分类: 算法 发布时间: 2015-03-28 17:12 ė 6 没有评论

前几天看姜启源的《数学模型》,看到第一章里的第二个关于 商人过河的模型,突然想到前几天在FUZOJ上做的月赛最后两道题,觉得很有意思,于是回去把它们给补了。

《数学模型》中的商人过河案例是这样的:有3名商人带着3名随从过一条河,过河仅有一条能容纳2人的船,由他们自己划行,三名随从密定,一旦在河的任意一岸随从人数大于商人人数,他们就杀人越货。但是坐船的方案由商人决定,商人们怎样才能安全的过河呢?

FUZOJ月赛的题目则与这道题极为相似。

倒数第二题(FUZOJ2188):小明要把x只羊和y只狼运到河对岸,船上最多容纳n只动物且至少要有一只动物,无论在岸上还是船上,如果狼数量大于羊数量,浪就会把羊吃掉。求没有羊被吃掉,小明至少要划几次船,如果无法完成则输出-1。(0≤ x, y, n ≤ 200)

见到这个题目我的第一反应是关于图论的题目,高中时候学图论建图的时候讲过一个小学生都知道的狼、羊、白菜模型,那个模型通过确定河这岸狼、羊、白菜的情况生成一个状态,每划一次船就改变一次状态,于是两个状态之间就产生了一条有向边,然后图就建成了。

其实这道题也用到了类似的想法,只是没有建出一个完整的图,毕竟对于200的数据量,要生成的边有点多。讲到这里我可以开始说一下我的思路了。

首先建模,记第k次渡河前此岸的羊和狼的数量为xk,yk,(k=1,2,3…,xi=0,1,2,…,x,yi=0,1,2,3,…,y),将二维向量sk=(xk,yk)定义为一个状态。那么安全渡河条件下所有的状态就构成了允许状态集合S。

接着,记第k次渡河时船上羊和狼的数量为ukvk(1<=uk+vk<=n),将二维向量dk=(uk,vk)定义为一个决策,那么所有决策构成了允许决策集合D。

显然k为奇数的时候船由此岸划向彼岸,k为偶数时船由彼岸划向此岸,所以状态随决策的变化即状态转移方程为

sk+1=sk+(-1)k dk

说到状态转移方程我们就会想到dp,我觉得理论上dp是能够做这道题的,但是作为一个lowB,感觉要写四层循环就没敢写,我用的是BFS。

对于一道编程题来说,我其实只要写上BFS或者暴力就完全可以作为这道题的题解,

但既然我啰嗦了这么多,就没有把这道题简单地看做一道编程题。

现在,让我们把建模进行到底。

将抽象的S集合放进平面直角坐标系中考虑,每个状态即对应了坐标系中的一个整点,初始状态在点(x0,y0),题目则是求通过有限步决策使点转移到(0,0)。

2015032

最后,是否所有状态和所有决策都是有效的呢?显然不是,因为狼比羊多时狼可以吃羊,这种状态就是无效的。对于有效的状态,此岸羊(xk)不少于(>=)狼(yk),右岸羊(x0-xk)不少于(>=)狼(y0-yk),加上0<=xk<=x0和0<=yk<=y0,就得到了几个不等式,坐标系+不等式,我们可以采用线性规划确定有效状态。还有一种特殊状态是任意一岸没有狼或者羊,通过计算我们可以将这些状态取并得到如下的可行域:

2015031

对于有效的决策,只需要满足uk>=vk且状态sk+1有效

下面给出样例3 3 2=>11的决策情况(橙色点为可行点)我好仰慕我的P图水平啊

2015033

这道题还有一点需要注意,对初始状态即(x0,y0)需要判断是否有效,否则直接输出-1。

View Code

这道题限时3000MS,我的代码1600+MS过,但翔神告诉我还有O(1)的做法,我立马想到了打表找规律,在坚持不懈的探索下我终于把规律找全。献上我的0MS代码

View Code

FZUOJ2189处理的是这道题x=y的特殊情况,但是数据量扩大到了200000。虽然智商有限,那些高端做法与我无缘,但是在上题打表找出规律后,再大的数据都不成问题了,只要抠出上一段代码里的一部分就能轻松过。

打表不是万能的,但没有打表是万万不能的。

本文出自shad0w_walker,转载时请注明出处及相应链接。

本文永久链接: https://www.sdwalker.com/archives/72.html

0

发表评论

电子邮件地址不会被公开。 必填项已用*标注

返回顶部