建模思想的一点点应用（另：打表大法好！）

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

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

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

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

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

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

首先建模，记第k次渡河前此岸的羊和狼的数量为x_k，y_k，（k=1,2,3…，x_i=0,1,2,…,x，y_i=0,1,2,3,…,y），将二维向量s_k=（x_k，y_k）定义为一个状态。那么安全渡河条件下所有的状态就构成了允许状态集合S。

接着，记第k次渡河时船上羊和狼的数量为u_k，v_k（1<=u_k+v_k<=n），将二维向量d_k=（u_k，v_k）定义为一个决策，那么所有决策构成了允许决策集合D。

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

s_k+1=s_k+（-1）^k d_k

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

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

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

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

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

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

对于有效的决策，只需要满足u_k>=v_k且状态s_k+1有效

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

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

View Code

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

View Code

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

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