经过了一段时间的努力，我再Pku上也算是有了一个阶段性的总结拉，下面是我就这段时间搞ACM来的一些代码的总结，具体的一些题目类型的总结看本Blog的相关文章。 huicpc26 ACM_PKU 代码总结 1、DP（动态规划）/*1080-HumanGeneFunctions.cpp*/观察题目给出的一个最优解： AGTGATG -GTTA-G 将其从某一处切开，如果左边部分的分值不是最大，那么将其进行调整，使其分值变大，则整个解分值变大，与已知的最优矛盾。所以左边部分的分值必是最大。同理，右边也是。可见满足最优子结构的性质。考虑使用DP： 设两个DNA序列分别为s1，s2，长度分别为len1，len2，score为分值表。f[i,j]表示子串s1[1..i]和s2[1..j]的分值。考虑一个f[i,j]，我们有： 1.s1取第i个字母，s2取“-”：f[i-1,j] + score[s1[i],''-''] 2.s1取“-”，s2取第j个字母：f[i,j-1] + score[''-'',s2[j]] 3.s1取第i个字母，s2取第j个字母：f[i-1,j-1] + score[s1[i],s2[j]] 即f[i,j] = max(f[i-1,j] + score[s1[i],''-''], f[i,j-1] + score[''-'',s2[j]], f[i-1,j-1] + score[s1[i],s2[j]]); 然后考虑边界条件，这道题为i或j为0的情况。 当i=j=0时，即为f[0,0]，这是在计算f[1,1]时用到的，根据f[1,1] = f[0,0] + score[s1[i], s2[j]]，明显有f[0,0] = 0。 当i=0时，即为f[0,1..len2]，有了f[0,0]，可以用f[0,j] = f[0,j-1] + table[''-'',s2[j]]来计算。 当j=0时，即为f[1..len1,0]，有了f[0,0]，可以用f[i,0] = f[i-1,0] + table[s1[i],''-'']来计算。 至于计算顺序，只要保证计算f[i,j]的时候，使用到的f[i-1,j]，f[i,j-1]，f[i-1,j-1]都计算出来了就行了。所谓划分阶段也就是为了达到这个目的。这样我们使用一个二重循环就可以了。*/#include #include #include using namespace std;#define MAX(a,b,c) (a>b?a:b)>c?(a>b?a:b):cint ctoi(char a){ int b; if(a==''A'') b = 0; if(a==''C'') b = 1; if(a==''G'') b = 2; if(a==''T'') b = 3; if(a==''-'') b = 4; return b;}int main(){ int t,j,k,m,n; int f1,f2,f3; int f[101][101];int arr[5][5]={{5,-1,-2,-1,-3},{-1,5,-3,-2,-4},{-2,-3,5,-2,-2},{-1,-2,-2,5,-1},{-3,-4,-2,-1,0}}; string a,b; cin>>t; while(t--){ j = k = 0; memset(f,0,sizeof(f)); cin>>m>>a; cin>>n>>b; for(j=0;j<=m;j++) { for(k=0;k<=n;k++) { if(j == 0 && k == 0) { f[j][k] = 0; } else if(j==0) { f[j][k] = f[j][k-1] + arr[ctoi(''-'')][ctoi(b[k-1])]; } else if(k==0) { f[j][k] = f[j-1][k] + arr[ctoi(a[j-1])][ctoi(''-'')]; } else { f1 = f[j-1][k] + arr[ctoi(a[j-1])][ctoi( ''-'')]; f2 = f[j][k-1] + arr[ctoi( ''-'')][ctoi(b[k-1])]; f3 = f[j-1][k-1] + arr[ctoi(a[j-1])][ctoi(b[k-1])]; f[j][k] = MAX(f1,f2,f3); } } } cout<
评论