第二次算法上机-POJ1050 1080 1141.doc

第一次算法实验报告POJ1050 To the Max1） 题目:Time Limit：1000MS Memory Limit：10000KDescriptionGiven a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1*1 or greater located within the whole array. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle. As an example, the maximal sub-rectangle of the array: 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 is in the lower left corner: 9 2 -4 1 -1 8 and has a sum of 15. InputThe input consists of an N * N array of integers. The input begins with a single positive integer N on a line by itself, indicating the size of the square two-dimensional array. This is followed by N2 integers separated by whitespace (spaces and newlines). These are the N2 integers of the array, presented in row-major order. That is, all numbers in the first row, left to right, then all numbers in the second row, left to right, etc. N may be as large as 100. The numbers in the array will be in the range -127,127.OutputOutput the sum of the maximal sub-rectangle.Sample Input40 -2 -7 0 9 2 -6 2-4 1 -4 1 -18 0 -2Sample Output152）解题分析： 对于单列数，求任意连续若干个数和的最大值。很好解决。而对于多列数，可以考虑将其转换成单列数字来做。将从第i行到第j行的数相同列的数叠加就起到了压缩的效果。然后当做单列数解决就行了。求最大子段和可用动态规划算法。3）算法设计：1、对于单列数，因为是连续若干个自然数的和，那么，前面的某个数字取与不取的条件在于：以前面这个数字为结尾的连续数的和最大值是否大于0，如果大于0，那么这个数字必然要会出现在包括数字的序列中，否则无法做到最大。处理的原则是maxni=max0,maxni-1+ai;2、对于多列数，引入辅助数组st,stij代表第i列从第1行开始的数字累加到第j行的值。那么，我们每次压扁的时候，就可以用stij-stik-1来表示第i列从第k个数字累加到第j个数字的值。达到压缩的效果。然后用上面单列数字的方法来做。算法时间复杂度O(N3)4）程序代码：#include #include #define mt 101int main()int amtmt;int stmtmt;int p,k,n,i,j,sum,maxn;scanf(%d,&n);for (i=1;i=n;i+)for (j=1;j=n;j+)scanf(%d,&aij);memset(st,0,sizeof(st);for (i=1;i=n;i+) for (j=1;j=n;j+) stij=stij-1+aji; maxn=0; for (i=1;i=n;i+) for (j=i;j=n;j+) p=st1j-st1i-1;sum=p;for (k=2;k0)sum+=stkj-stki-1;else sum=stkj-stki-1;if (sump) p=sum;if (pmaxn)maxn=p;printf(%dn,maxn); return 0; 5）实验结果及其分析： a) 代码必须在Poj上通过。通过的代码，Poj有Accepted提示，截屏，把拷屏的图粘贴到实验报告中:b)测试数据，运行结果: c) 实验结果分析： 从结果上看，当用poj的样例数据进行测试时,程序可以得出正确的结果。6）实验心得： 在本次实验中关键地方有两处，一是将多列数转化为单列数得到化繁为简的效果；二是在求最大子段和时用动态规划算法。前者是巧妙的想法，后者是已经学习的知识。所以我们应当掌握前人探索出的知识，然后才能更好的创新。POJ1080 Human Gene FunctionsTime Limit: 1000ms Memory Limit: 10000k题目:DescriptionIt is well known that a human gene can be considered as a sequence, consisting of four nucleotides, which are simply denoted by four letters, A, C, G, and T. Biologists have been interested in identifying human genes and determining their functions, because these can be used to diagnose human diseases and to design new drugs for them. A human gene can be identified through a series of time-consuming biological experiments, often with the help of computer programs. Once a sequence of a gene is obtained, the next job is to determine its function. One of the methods for biologists to use in determining the function of a new gene sequence that they have just identified is to search a database with the new gene as a query. The database to be searched stores many gene sequences and their functions many researchers have been submitting their genes and functions to the database and the database is freely accessible through the Internet. A database search will return a list of gene sequences from the database that are similar to the query gene. Biologists assume that sequence similarity often implies functional similarity. So, the function of the new gene might be one of the functions that the genes from the list have. To exactly determine which one is the right one another series of biological experiments will be needed. Your job is to make a program that compares two genes and determines their similarity as explained below. Your program may be used as a part of the database search if you can provide an efficient one. Given two genes AGTGATG and GTTAG, how similar are they? One of the methods to measure the similarity of two genes is called alignment. In an alignment, spaces are inserted, if necessary, in appropriate positions of the genes to make them equally long and score the resulting genes according to a scoring matrix. For example, one space is inserted into AGTGATG to result in AGTGAT-G, and three spaces are inserted into GTTAG to result in GT-TAG. A space is denoted by a minus sign (-). The two genes are now of equal length. These two strings are aligned: AGTGAT-G -GT-TAG In this alignment, there are four matches, namely, G in the second position, T in the third, T in the sixth, and G in the eighth. Each pair of aligned characters is assigned a score according to the following scoring matrix. denotes that a space-space match is not allowed. The score of the alignment above is (-3)+5+5+(-2)+(-3)+5+(-3)+5=9. Of course, many other alignments are possible. One is shown below (a different number of spaces are inserted into different positions): AGTGATG -GTTA-G This alignment gives a score of (-3)+5+5+(-2)+5+(-1) +5=14. So, this one is better than the previous one. As a matter of fact, this one is optimal since no other alignment can have a higher score. So, it is said that the similarity of the two genes is 14. InputThe input consists of T test cases. The number of test cases ) (T is given in the first line of the input file. Each test case consists of two lines: each line contains an integer, the length of a gene, followed by a gene sequence. The length of each gene sequence is at least one and does not exceed 100. OutputThe output should print the similarity of each test case, one per line. Sample Input2 7 AGTGATG 5 GTTAG 7 AGCTATT 9 AGCTTTAAA Sample Output1421 2） 解题分析：题意是给两串DNA序列，按照给定的方法找他们最大的相似度。本题采用由低到高的往上递推，用动态规划的算法。3） 算法设计：以1、2、3、4、5分别代替A、C、G、T、-。设d(i,j)为第一个序列(a)的前i个数和第二个序列(b)的前j个数的相似度的最大值。当ai+1=bj+1时，由题目给出的表显然可以得出f(i+1,j+1)=f(i,j)+cs1i+1s2j+1;c组为题目中给出的那个表格。当ai+1!=bj+1时，反证法显然有f(i+1,j+1)=max(f(i,j)+cai+1bj+1,f(i,j+1)+cai+15,c(i+1,j)+c5bj+1)。于是，两个for就解决问题了。4）程序代码： #includeint f510510;int main() int i,j,k,t1,t2,c10010,a1110,b1110,n; char x; c11=5; c12=-1; c13=-2; c14=-1; c15=-3; c21=-1; c22=5; c23=-3; c24=-2; c25=-4; c31=-2; c32=-3; c33=5; c34=-2; c35=-2; c41=-1; c42=-2; c43=-2; c44=5; c45=-1; c51=-3; c52=-4; c53=-2; c54=-1; c55=0; scanf(%d,&n); scanf(%c,&x); for(i=1;i=n;i+) scanf(%d%c,&t1,&x); for(j=1;j=t1;j+) scanf(%c,&x); if (x=A) aj=1; if (x=C) aj=2; if (x=G) aj=3; if (x=T) aj=4; scanf(%c,&x); scanf(%d%c,&t2,&x); for(j=1;j=t2;j+) scanf(%c,&x); if (x=A) bj=1; if (x=C) bj=2; if (x=G) bj=3; if (x=T) bj=4; for(j=0;j=t1;j+) for(k=0;k=t2;k+) fjk=-100000000; f00=0; for(j=1;j=t1;j+) fj0=fj-10+caj5; for(j=1;j=t2;j+) f0j=f0j-1+c5bj; for(j=1;j=t1;j+) for(k=1;kfjk) fjk=fj-1k-1+cajbk; if (fjk-1+c5bkfjk) fjk=fjk-1+c5bk; if (fj-1k+caj5fjk) fjk=fj-1k+caj5; printf(%dn,ft1t2); return 0;5）实验结果及其分析： a) 代码必须在Poj上通过。通过的代码，Poj有Accepted提示，截屏，把拷屏的图粘贴到实验报告中：b) 测试数据，运行结果:c) 实验结果分析： 从实验数据来看，程序在输入为样例数据和编造的没有可行解的数据时均得到了正确的答案，可初步断定程序是正确的。 6）实验心得： 本实验程序的关键之处在于采取由低到高的往上递推，动态规划的算法。另外实验为了表达方便以数字12345代替AGCT-，不替代也很简洁的，只是依各人喜好来。POJ1141 Brackets SequenceTime Limit: 1000ms Memory Limit: 65536题目:DescriptionLet us define a regular brackets sequence in the following way: 1. Empty sequence is a regular sequence. 2. If S is a regular sequence, then (S) and S are both regular sequences. 3. If A and B are regular sequences, then AB is a regular sequence. For example, all of the following sequences of characters are regular brackets sequences: (), , (), (), (), ()() And all of the following character sequences are not: (, , ), )(, (), ( Some sequence of characters (, ), , and is given. You are to find the shortest possible regular brackets sequence, that contains the given character sequence as a subsequence. Here, a string a1 a2 . an is called a subsequence of the string b1 b2 . bm, if there exist such indices 1 = i1 i2 . in = m, that aj = bij for all 1 = j = n.InputThe input file contains at most 100 brackets (characters (, ), and ) that are situated on a single line without any other characters among them.OutputWrite to the output file a single line that contains some regular brackets sequence that has the minimal possible length and contains the given sequence as a subsequence.Sample Input(Sample Output()()4） 解题分析：题意是给出一个括号序列，求能够得到的最短合法序列注：空序列是合法序列；若A合法，则A、(A)合法;若A、B均合法,则AB合法。采用区间动态规划算法。5）算法设计：fi,j表示ij区间所需要添加的最少括号数，则可得：当si与sj是合法时，fi,j := min(fi,j,fi+1,j-1);也就是不用添加当si= (时，fi,j := min(fi,