题意:
给出字符串个数 n
给出n串字符串
找出上下两个字符串重复和最多的个数..
eg:
5 abc bcd cde aaa bfcde 0
根据
aaa
abc
bcd
cde
bfcde
答案就是重复的 a bc cd cde
思路:
因为状态很少..最多只有10 个字符串~而每个字符串最多 10 个字符..
所以可以用状态DP来实现..
dp[ sta ][ i ] 表示 在sta 状态下以第 i 串字符串结尾的最优解..
sta 用 (1<<n)-1 表示..其中变成二进制后1表示有这个状态 0 表示没有这个状态..
基本算法:
①. 根据给出的 n 确定 sta
②. 根据给出的数据确定辅助数组 f[ i ][ j ] 表示第 i 串接第 j 串的重复字符个数
③. 把dp 初始化为某一个值..表示不可达到的情况..
④. 给已知情况给dp 赋已知可达到情况的值..
⑤. for(i:1~sta)
for(j: 0~n)
if(i 中包含 j这个状态)
for(k: 0~n)
if(i 中不包含 k 这个状态)
dp[state][ k ] = max/min(dp[state][k], dp[ i ][ j ] + f[ j ][ k ]) //实现dp的状态转移
⑤. 根据dp[sta][] 中的各种情况找出需要的答案~
Tips:
state = 2^n -1
for 循环中找的时候从 1 开始找~
还有对我来说就是 找出两个字符串重复的个数..
囧~我这个弱菜真的很纠结暴搜的过程吖~各种细节错..
※※
一些二进制的基本知识:
判断j是否属于集合i:i&(1<<j)
在集合i中去除j:i-(1<<j)或者i&(!(1<<j)) i^(1<<j)
在集合i中加入点j:i|(1<<j);
Code:
View Code
1 #include <stdio.h> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 #define clr(x) memset(x, 0, sizeof(x)) 6 #define max(a, b) (a)>(b)?(a):(b) 7 const int INF = 0x1f1f1f1f; 8 9 int dp[1<<15][15], f[15][15]; 10 char arr[15][15]; 11 12 int lenn(char *a, char *b) 13 { 14 int lena = strlen(a), lenb = strlen(b); 15 int max = 0; 16 int sum; 17 for(int i = 0; i < lena; ++i){ 18 sum = 0; 19 for(int j = 0; j < lenb && i+j < lena; ++j){ 20 if(a[i+j] == b[j]) sum++; 21 } 22 if(sum > max) max = sum; 23 } 24 25 for(int i = 0; i < lenb; ++i){ 26 sum = 0; 27 for(int j = 0; j < lena && i+j < lenb; ++j) 28 if(b[i+j] == a[j]) sum++; 29 if(sum > max) max = sum; 30 } 31 return max; 32 } 33 34 int main() 35 { 36 int i, j, k; 37 int n, st, sta; 38 while(scanf("%d", &n) != EOF) 39 { 40 if(n == 0) break; 41 clr(f), clr(dp); 42 st = (1<<n) - 1; 43 44 for(i = 0; i < n; ++i) 45 scanf("%s", arr[i]); 46 47 for(i = 0; i < n; ++i) 48 for(j = 0; j < n; ++j) 49 if(i != j){ 50 f[i][j] = f[j][i] = lenn(arr[i], arr[j]); 51 } 52 53 memset(dp, -1, sizeof(dp)); 54 for(i = 0; i < n; ++i) 55 dp[1<<i][i] = 0; 56 57 for(i = 1; i < st; ++i) 58 for(j = 0; j < n; ++j) 59 if(dp[i][j] != -1) 60 for(k = 0; k < n; ++k) 61 if(!(i&(1<<k))){ 62 sta = i+(1<<k); 63 dp[sta][k] = max(dp[sta][k], dp[i][j]+f[j][k]); 64 } 65 66 int ans = 0; 67 for(i = 0; i < n; ++i) 68 if(dp[st][i] > ans) ans = dp[st][i]; 69 70 printf("%d\n", ans); 71 72 73 } 74 return 0; 75 }