取消网站备案时间,网站开发后台框架,宁波seo推广咨询,做图的兼职网站题意:给出N(N10)个字符串(length10),定义两个串a,b之间的公共序列长度为 将a,b对齐后,相同位置上相同字母的个数,a,b的最长公共序列长度自然是相同字母数的 最大值,如aabcd,bbed,a,b的最长公共序列长度为2. 如要求将N个字符串排列,使得相邻的N-1对字符串的最长公共序列…题意:给出N(N10)个字符串(length10),定义两个串a,b之间的公共序列长度为 将a,b对齐后,相同位置上相同字母的个数,a,b的最长公共序列长度自然是相同字母数的 最大值,如aabcd,bbed,a,b的最长公共序列长度为2. 如要求将N个字符串排列,使得相邻的N-1对字符串的最长公共序列长度和最大. (出题人不负责,N怎么也应该有20,这题暴搜可以过.) 讲讲状压的做法. f[i,j]中j(二进制)表示哪些字符串已选,i表示最右边的是哪一个字符串. 转移时,枚举j中的一个不为0的位,去掉,成为j,i表示j中所有不为0的位, 则f[i,j]max{f[i,j]LCS(s[i],s[i])} ((j(i-1))11) (LCS是上面定义的那种). ansmax{f[i,1n-1]} (1in) code: type stringxstring[11];
var f:array[0..11,0..1100] of longint;g:array[0..11,0..11] of longint;s:array[0..11] of stringx;n,i,j,opt,now,ans:longint;function max(a,b:longint):longint;beginif ab then exit(a); exit(b);end;function work(a,b:stringx):longint;var p,q,la,lb,l,c,maxl:longint;beginmaxl:0;la:length(a);lb:length(b);for p:1 to la dofor q:1 to lb dobeginl:0;c:0;while (plla)and(qllb) dobeginif a[pl]b[ql] then inc(c);inc(l);end;if cmaxl then maxl:c;end;exit(maxl);end;function check(num:longint):boolean;var c:longint;beginc:0;while num0 dobegininc(c,num and 1);num:num1;end;exit(c1);end;beginwhile not seekeof dobeginreadln(n);if n0 then break;for i:1 to n do readln(s[i]);for i:1 to n-1 dofor j:i1 to n dobeging[i,j]:work(s[i],s[j]);g[j,i]:g[i,j];end;fillchar(f,sizeof(f),171);for i:1 to n do f[i,1(i-1)]:0;for opt:1 to 1n-1 doif check(opt) thenfor i:1 to n doif (opt(i-1)) and 11 thenbeginnow:opt xor (1(i-1));for j:1 to n doif (now(j-1)) and 11 thenf[i,opt]:max(f[i,opt],f[j,now]g[j,i]);end;ans:0;for i:1 to n doans:max(ans,f[i,1n-1]);writeln(ans);end;
end.note:求最大权哈密顿回路可以用状态压缩的方法,类似此题. 另外一些摆放类的问题求最值也可以用状压(以后会写).转载于:https://www.cnblogs.com/exponent/archive/2011/08/07/2130146.html
