信息学集训队作业0070-dna

题目0070–DNA（DNA序列密码问题）题目来源：Other推荐者：许智磊英文原文二、中文翻译DNA序列密码问题问题描述： 一些生物的复杂结构可以用其DNA序列来表示。而DNA序列又可表示为带有标记的核苷酸字符串。最近，福州大学信息学院生物信息学研究小组的一项工作表明，大多数蛋白质序列可以从核苷酸数据库记录中推导出来。研究小组的科学家们用密码学方法将DNA序列变换为2维Cray码后发现，任一DNA的Cray码序列S具有如下性质：列S：（x1，y1），（x2，y2），…，（xn，yn）是一个有限序列；列S中各项（xi，yi）均落在一个网格边长为1的300×3000平面网格N的网格点上；3．序列S中各项最多分布在网格N的3行中。科学家们发现，若将序列S的每一项都看作平面上一个点，从序列的任意一点出发，连接序列中每个点恰好一次，又回到出发点的最短平面回路T的长度与该序列表示的DNA密码密切相关。为了有效地破译DNA密码，科学家们希望设计出一个高效的计算程序，能对给定DNA的Cray码序列S，快速计算出其最短回路T的长度。 编程任务：对于给定的DNA的Cray码序列S，计算出其最短回路T的长度。数据输入：Cray码序列S依其在网格N中的位置分为3行：(a1,ya),(a2,ya),…,(ana,ya);(b1,yb),(b2,yb),…,(bnb,yb);(c1,yc),(c2,yc),…,(cnc,yc)。其中0≤ya<yb<yc≤300分别是3行的纵坐标。0≤na，nb，nc≤1300；分别是各行中的点数。各行中点依其横坐标从小到大排列。0≤a1<a2<…<ana≤3000;0≤b1<b2<…<bnb≤3000；0≤c1<c2<…<cnc≤3000.输入数据由文件名为INPUT3.*的文本文件提供。●第1行中的3个整数为na，nb和nc； ●第2行中的3个整数为ya，yb和yc；●接下来的na行中每行一个整数，依次为a1，a2，…，ana；●再接下来的nb行中每行一个整数，依次为b1，b2，…，bnb；●最后的nc行中每一个整数，依次为c1，c2，…，cnc。 结果输出程序运行结束时，在屏幕上输出所找到的序列S的最短回路T的长度值，精确到小数点后2位。输入文件示例 输出示例 INPUT3.001 8.832121235 7657三、初步讨论情况姜尚仆动态规划方奇动态规划高正宇动态规划陆可昱四边形不等式??项荣璟感觉可以用动态规划，可能要分几种情况，比较麻烦。还没想清楚。伍昱应该可以用动态规划好像还可以用四边形不等式加速邵煊程由于最短回路有一定的构形，因此可以用动态规划解决。张云亮因为只有三行，所以可以用动态规划，看中间一行的点是属于找出哈密尔顿回路的上分支还是下分支。雷环中目前不会做。已知一种O(N^3)的动态规划算法，最后一个测试点可以3秒钟出解（时限60秒），不过算法实现起来比较麻烦，肯定有更好的算法。许智磊最短的路肯定没有交叉，所以先求外围轮廓，然后在某些地方凹进去，采用动态规划，而且可以用四边形不等式来优化。刘才良回路不能自交，否则不是最优，由此可以看出问题主要就在第二行的点的安排，这个可以用动态规划解决，时间复杂度O(N3)张宁利用几何性质，我们可以用动态规划解决此题，并且可以利用四边形不等式，我们可以把时间复杂度从O(n^3)降到O(n^2)林希德DP好了，四边形优化后复杂度可以从O(n3)降到O(n2)王知昆在平面上的最优哈密尔顿回路一定不存在两条边相交。利用这个性质可以设计出动态规划算法。首先，求凸包（实际上就是将1，3两行的点和第二行头尾两个点串起来），然后对于第二行中的每一个点，判断它的连接方案。有两种情况，一是从第二行它前面的点连接到它，二是从凸包上的一个点连接到它。这样可以用动态规划解决社d[i]表示第二行前i个点（如果第一个点在凸包上，就要把第一个点除去）连接到凸包上的最小距离和。d[i]=min(d[j]+s[i,j,k]),j<i说明：s[i,j,k]表示将第二行中的点i到点j连接到凸包的第k个点和第k＋1个点之间的长度。刘一鸣题目中的Hamilton回路可以用两条不相交的路径来表示（若相交一定不是最优解）。令一条路径连结第1行的点和第2行的若干个点，另一条路径连结第3行的点第2行的其它点。---*--*--\\---*+---*--\\*----------问题的关键就在于第2行的安排。如上图，在“+”表示的点的左侧第2行的点在第1条路径中，右侧在第2条路径中。由此，假设第2行的点数为n，设f[n,k]（1<=k<=2）表示第2行的第n个点由第k条路径来连之前的最优值。可以得到状态转移方程：f[n,k]=min{f[i,3-k]+cost[i,3-k,n,k]}cost[i,3-k,n,k]表示(i,3-k)到(n,k)状态值的差，也就是中间点的总路程。这个值可以在预处理的时候算出来。由状态转移方程不难看出，DP的时间复杂度是O(n2)。金恺由于最短Hamilton回路（以下简称H）满足一个特性：任意两条边都不相交，再加上本题特殊的条件：所有点都处于3行上，所以H的外形是很有特点的（如右图）：可以看成将凸包的某些边凹进去形成的一条回路，而且凹进去的是一个个的梯形（三角形可以看成某底边长为0的梯形）。因此，H的长度=凸包的边长+某些边凹进去时增加的长度，要使H的长度最小，也就是使增加的长度最小，同时还要保证中间一排的点都在H上。利用这些特点可以采用动态规划来解决：设Fi表示第二排中，前i个点都以连接到了H上，最少需要新增的长度，显然有Fi=Fj–1+(X2,i–X2,j)+Min{Dis(X2,j,Y2,X1,k,Y1)+Dis(X2,i,Y2,X1,k+1,Y1),Dis(X2,j,Y2,X3,k,Y3)+Dis(X2,i,Y2,X3,k+1,Y3)}上述方程中有两个未知量j、k，但k的确定是满足四边形不等式的，因此总的复杂度为O(N2)。饶向荣很明显，我们可以先将路线定为围着第一行和第三行的所有点形成的环，然后可对此环作凹入处理，使得环包括第二行上的点，而且凹入的各部分之间比不相交，也就是说前面的凹入对后面无影响，即无后效性，那么考虑用动态规划，表示第二行的前个点都被凹入的最短路，那么状态转移方程为：f[i]=min{f[j-1]+mc[j,i],1≤j≤i}其中的表示对第二行的第j个点到第i个点凹入的最短方案值，这个可以提前算出来,它的计算满足四边形不等式，时间复杂度为O(N2)。此算法的总复杂度为O(N2)。何林凡是这类平面点的hamilton问题，都有一个重要的性质：连线不相交。证明很容易，略去。因此先把凸包求出来（这个题凸包很特殊，所以O(n)就能简单的搞定）。凸包必然包含上、下两条与x轴平行的边。（也就是题目中点分布的上下两