前几天看姜启源的《数学模型》,看到第一章里的第二个关于 商人过河的模型,突然想到前几天在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次渡河时船上羊和狼的数量为uk,vk(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)。
最后,是否所有状态和所有决策都是有效的呢?显然不是,因为狼比羊多时狼可以吃羊,这种状态就是无效的。对于有效的状态,此岸羊(xk)不少于(>=)狼(yk),右岸羊(x0-xk)不少于(>=)狼(y0-yk),加上0<=xk<=x0和0<=yk<=y0,就得到了几个不等式,坐标系+不等式,我们可以采用线性规划确定有效状态。还有一种特殊状态是任意一岸没有狼或者羊,通过计算我们可以将这些状态取并得到如下的可行域:
对于有效的决策,只需要满足uk>=vk且状态sk+1有效
下面给出样例3 3 2=>11的决策情况(橙色点为可行点)我好仰慕我的P图水平啊
这道题还有一点需要注意,对初始状态即(x0,y0)需要判断是否有效,否则直接输出-1。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
|
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; struct node{ int x,y,step; }; int n; bool visit[2][201][201]; int BFS(int x,int y) { int i,j,sign; queue<node> qu; node tmp,now; tmp.x=x;tmp.y=y; tmp.step=0; visit[0][x][y]=1; qu.push(tmp); while(!qu.empty()){ now=qu.front(); qu.pop(); //printf(" %d %d %d\n",now.x,now.y,now.step); if(now.x==0&&now.y==0) return now.step; sign=(now.step%2)?1:-1; tmp.step=now.step+1; for(i=1;i<=n;i++){ //if(i!=1&&sign==1) break; for(j=0;j<=i;j++) if(j>=i-j||j==0||i==j){ tmp.x=now.x+sign*j; tmp.y=now.y+sign*(i-j); if(tmp.x>x||tmp.x<0|tmp.y>y||tmp.y<0||visit[tmp.step%2][tmp.x][tmp.y]) continue; if((tmp.x>=tmp.y&&tmp.y-tmp.x>=y-x)||tmp.x==0||tmp.x==x){ visit[tmp.step%2][tmp.x][tmp.y]=1; qu.push(tmp); } } } } return -1; } int main() { int x,y; while(~scanf("%d%d%d",&x,&y,&n)){ if(x<y&&x){ printf("-1\n"); continue; } memset(visit,0,sizeof(visit)); printf("%d\n",BFS(x,y)); } return 0; } |
这道题限时3000MS,我的代码1600+MS过,但翔神告诉我还有O(1)的做法,我立马想到了打表找规律,在坚持不懈的探索下我终于把规律找全。献上我的0MS代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
|
#include<iostream> #include<cstdio> using namespace std; int f(int m,int n) { if(m==0) return 0; if(n==1) return -1; if(n==2){ if(m==1) return 1; if(m==2) return 5; if(m==3) return 11; return -1; } if(n==3){ if(m==1) return 1; if(m==2) return 3; if(m==3) return 5; if(m==4) return 9; if(m==5) return 11; return -1; } m-=n/2; if(m<=0) return 1; m-=(n-1)/2; if(m<=0) return 3; m-=(n-2)/2; if(m<=0) return 5; m-=(n-1)/2; if(m<=0) return 7; return (m-1)/((n-2)/2)*2+9; } int ff(int x,int y,int n) { if(x+y==0) return 0; if(x>y){ if(x+y<=n) return 1; else return (x+y-2)/(n-1)*2+1; } if(x==0){ if(y==1) return 1; else return (y-2)/(n-1)*2+1; } if(x==y) return f(x,n); return -1; } int main() { int x,y,n; while(~scanf("%d%d%d",&x,&y,&n)){ printf("%d\n",ff(x,y,n)); } return 0; } |
FZUOJ2189处理的是这道题x=y的特殊情况,但是数据量扩大到了200000。虽然智商有限,那些高端做法与我无缘,但是在上题打表找出规律后,再大的数据都不成问题了,只要抠出上一段代码里的一部分就能轻松过。
打表不是万能的,但没有打表是万万不能的。
本文出自shad0w_walker,转载时请注明出处及相应链接。
本文永久链接: https://www.sdwalker.com/archives/72.html