题解：字符配对

Aurora

Guderian出品

说明

给定一个字符$B=b_1 b_2\dots b_n$，其中$b_i \in \{A,C,G,U\}$。$B$上的二级结构是一组字符对集合$S=\{(b_i,b_j)\}$，其中$i,j\in \{1,2,\dots ,n\}$，并满足以下四个条件：

（1）$S$中的每对字符是$(A,U),(U,A),(C,G),(G,C)$四种组合之一；

（2）$S$中的每对字符之间至少有四个字符将其隔开，即$i<j-4$；

（3）$S$中的每一个字符（记为$b_k$）的配对存在两种情况：$b_k$不参与任何配对；$b_k$和$b_t$配对，其中$t<k-4$；

（4）（不交叉原则）若$(b_i,b_j)$和$(b_k,b_l)$是$S$种的两个字符对，且$i<k$，则$i<k<j<l$不成立。

$B$的具有最大可能字符对数的二级结构$S$被称为最优配对方案，求解最优配对方案中的字符对数的方法如下：

假设用$C(i,j)$表示字符序列$b_i b_{i+1} \dots b_j$的最优配对方案（即二级结构$S$）中的字符对数，则$C(i,j)$可以递归定义为：

$C(i,j)=\begin{cases} \max(C(i,j-1),\max(C(i,t-1)+1+C(t+1,j-1))), &b_t和b_j匹配且i<j-4\\0 ，&\text{否则}\end{cases}$

分析

题目的第3个条件容易引起歧义，一种不影响作答的理解是：$B$上的字符要么不配对，要配对就要相隔至少4个字符。当然可以直接忽略这个条件，因为题目已经给出了足够多的信息了。

显然题目说明最后的方程是动态规划算法中的状态转移方程，这提示我们这道题目的算法思想是动态规划。因此我们采取的做法是：从较小的区间开始，转移到较大的区间，直到覆盖$B$中所有字符。

实现

（1）常量和变量说明

n：字符序列长度

B[]：字符序列

C[][]：最有配对数量数组

（2）C语言程序

不带主函数，未经调试

#include<stdio.h>
#include<stdlib.h>
#define LEN 100

/*判断两个字符是否配对*/
int isMatch(char a,char b) {
    if((a=='A'&&b=='U')||(a=='U'&&b=='A'))
        return 1;
    if((a=='C'&&b=='G')||(a=='G'&&b=='C'))
        return 1;
    return 0;
}

/*求最大配对数*/
int RNA_2(CHAR B[LEN],int n) {
    int i,j,k,t;
    int max;
    int C[LEN][LEN]={0};
    
    for(k=5;k<=n;i++){
        for(i=1;i<=n-k;i++){
            j=i+k;
            max=C[LEN][LEN];
            for(t=i;y<=j-4;t++){
                if(isMatch(B[t][j])&&max<C[i][t-1]+1+C[t+1][j-1])
                    max=C[i][t-1]+1+C[t+1][j-1];
            }
            C[i][j]=max;
            printf("C[%d][%d]=%d--",i,j,Ci][j]);
        }
    }
    return max;
}

（3）复杂度分析

时间复杂度：$O(n^3)$
空间复杂度：$O(n^2)$