Best Sequence(poj 1699) 状压dp（TSP） - c++编程基础

类似于前两天做的那个wordstack。状压的其实有时候爆搜+记忆化也差不多。

就是这个是要与之前的都重合，移位预处理要注意。

理解好第一个样例就行

/* ***********************************************
Author        :bingone
Created Time  :2014/12/9 22:48:56
File Name     :a.cpp
************************************************ */

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
          #include 
          
            #include 
           
             #include 
            
              #include 
             
               #define inf 0x3f3f3f3f #define maxn (10+10000) using namespace std; typedef long long ll; int N,M,T; char in[12][25]; int dp[1<<10][10]; int slen[10][10]; int len[10]; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); scanf("%d",&T); while(T--){ scanf("%d",&N); for(int i=0;i
              
               -1 && p>-1;t--,p--) if(in[i][p]!=in[j][t])break; else tmp++; if(tmp==len[i]-k) slen[i][j]=max(tmp,slen[i][j]); } else{ for(int t=len[j]-1,p=len[j]-1-k;t>-1 && p>-1;t--,p--) if(in[i][p]!=in[j][t])break; else tmp++; if(tmp==len[j]-k) slen[i][j]=max(tmp,slen[i][j]); } } } } int rt=1<
               
                /*
                3
2
ACCA
CC
5
TCGG
GCAG
CCGC
GATC
ATCG
3
TAC
ACT
TACTG

                
                ans:6 11 7 特别注意第一个样例的意思
                */