HDU 1080 DP LCS-白红宇

HDU 1080 DP LCS

阅读量：2443 次

发布时间：2019-05-10

本文共 2972 字，大约阅读时间需要 9 分钟。

/****************************************************************************************************    DP LCS,主要问题是那个i匹配0和0匹配j的处理，就是说i，j一开始就匹配'-'的情况，因为涉及到j匹配'-'的问题，所以不能去压缩成一维空间。。。****************************************************************************************************/#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #include 
                      
                       #include 
                       
                        #include 
                        
                         #include 
                         #include 
                          
                           using namespace std;#define LOWBIT(x) ( (x) & ( (x) ^ ( (x) - 1 ) ) )#define CLR(x, k) memset((x), (k), sizeof(x))#define CPY(t, s) memcpy((t), (s), sizeof(s))#define SC(t, s) static_cast
                           
                            (s)#define LEN(s) static_cast
                            
                             ( strlen((s)) )#define SZ(s) static_cast
                             
                              ( (s).size() )typedef double LF;//typedef long long LL; //GNU C++//typedef unsigned long long ULL;typedef __int64 LL; //Visual C++ 2010typedef unsigned __int64 ULL;typedef pair
                              
                                PII;typedef pair
                               
                                 PLL;typedef pair
                                
                                  PDD;typedef map
                                 
                                  ::iterator MI;typedef vector
                                  
                                   ::iterator VI;typedef list
                                   
                                    ::iterator LI;typedef set
                                    
                                     ::iterator SI;template 
                                     
                                      T sqa(const T &x){ return x * x;}template 
                                      
                                       T gcd(T a, T b){ if (!a || !b) { return max(a, b); } T t; while (t = a % b) { a = b; b = t; } return b;}template 
                                       
                                        T ext_gcd(T a, T b, T &x, T &y){ if (!b) { x = 1; y = 0; return a; } T d = ext_gcd(b, a % b, x, y); T t = x; x = y; y = t - a / b * y; return d;}template 
                                        
                                         T invmod(T a, T p){ LL inv, y; ext_gcd(a, p, inv, y); inv < 0 ? inv += p : 0; return inv;}const int INF_INT = 0x3f3f3f3f;const LL INF_LL = 0x7fffffffffffffffLL; //15fconst double oo = 10e9;const double eps = 10e-7;const double PI = acos(-1.0);#define ONLINE_JUDGEconst int MAXN = 1004;const int MAXC = 1 << 8;int test, n, m;string str, pat;int dp[MAXN][MAXN];int hs[MAXC][MAXC];void ace(){ hs['A']['A'] = 5; hs['A']['C'] = -1; hs['A']['G'] = -2; hs['A']['T'] = -1; hs['A']['-'] = -3; hs['C']['A'] = -1; hs['C']['C'] = 5; hs['C']['G'] = -3; hs['C']['T'] = -2; hs['C']['-'] = -4; hs['G']['A'] = -2; hs['G']['C'] = -3; hs['G']['G'] = 5; hs['G']['T'] = -2; hs['G']['-'] = -2; hs['T']['A'] = -1; hs['T']['C'] = -2; hs['T']['G'] = -2; hs['T']['T'] = 5; hs['T']['-'] = -1; hs['-']['A'] = -3; hs['-']['C'] = -4; hs['-']['G'] = -2; hs['-']['T'] = -1; hs['-']['-'] = -INF_INT; for (cin >> test; test--; ) { cin >> n >> str >> m >> pat; dp[0][0] = 0; for (int i = 1; i <= n; ++i) { dp[i][0] = dp[i - 1][0] + hs[ str[i - 1] ][ '-' ]; } for (int j = 1; j <= m; ++j) { dp[0][j] = dp[0][j - 1] + hs[ '-' ][ pat[j - 1] ]; } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { dp[i][j] = max( dp[i - 1][j - 1] + hs[ str[i - 1] ][ pat[j - 1] ], //str[i-1]和pat[j-1]去匹配 max( dp[i - 1][j] + hs[ str[i - 1] ][ '-' ], dp[i][j - 1] + hs[ '-' ][ pat[j - 1] ]) ); //str[i - 1]和'-'匹配 '-'和pat[j - 1]匹配 } } cout << dp[n][m] << endl; } return ;}int main(){#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin);#endif ace(); return 0;}