poj1699--Best Sequence（dfs+剪枝）

本文主要是介绍poj1699--Best Sequence（dfs+剪枝），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：点击打开链接

题目大意：给出n个字符串，要求组合后的串最短

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
char str[12][22] ;
char s[300] , s1[300] ;
int vis[12] , min1 , n , l[12];
void dfs(int cnt,int k) {//printf("%d %d\n", cnt, k) ;if( cnt >= min1 ) return ;if(k == n) {min1 = min(min1,cnt) ;return ;}int i , p , q , num ;for(i = 0 ; i < n ; i++) {if( vis[i] ) continue ;vis[i] = 1 ;for(p = max(0,cnt-l[i]) ; p <= cnt ; p++) {for(q = p ; q < cnt ; q++)if( str[i][q-p] != s[q] ) break ;if( q == cnt ) {num = cnt ;for(q = q-p ; q < l[i] ; q++)s[num++] = str[i][q] ;break ;}}dfs(num,k+1) ;vis[i] = 0 ;}return ;}
int main() {int t , i ;scanf("%d", &t) ;while( t-- ) {scanf("%d", &n) ;for(i = 0 ; i < n ; i++) {scanf("%s", str[i]) ;l[i] = strlen(str[i]) ;}min1 = 1000 ;memset(s,0,sizeof(s)) ;memset(vis,0,sizeof(vis)) ;dfs(0,0) ;printf("%d\n", min1) ;}return 0 ;
}

这篇关于poj1699--Best Sequence（dfs+剪枝）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---