题意描述

　　题目给出一些排成圆圈的渡口及若干摆渡路线，要求找出最多的不交叉的摆渡线路数。

　　算法分析

　　由于同时满足最优化原理和无后效性原则，所以本题可以用动态规划来解决。
　　设d[i,k]表示从第i个摆渡点起按顺时针方向的k个摆渡点间（不包含i本身）不交叉的最多线路数，则有
　　　　　d[i,k]=max{d[i,j]+d[(i+j-1) mod n+1,k-j]}+v[i,(i+k-1) mod n+1]
　　　　　(1<=j<k,v[a,b]代表摆渡点a和b之间直接相连的摆渡线路数)
　　最终的结果为：max{d[i,n-1]}。

　　参考程序