SRM589 DV1 250 回文字符串
其实这道题挺简单的,不过刚开始我钻了一个错误的死胡同。想明白之后才发现。 题目要求用最少的时间来将一个字符串变成回文字符串。(具体题目参看topcoder srm589 DV1 250分值的题目,不便公开以免影响后面做题的人)
首先对于(i,j),如果i=n-1-j, 那它们所代表的位置的字符最终必须相等,否则就不是回文了。S[i]=S[j];
如果源字符串S中,S[i]=S[j], 那么在最终的回文字符串中,它们必须还是相等。因为如果S[i]要变成其他字符,那么S[j]也必须跟着变。即它们要不都变,要不都不变。
可传递性:(i,j,k) 如果S[i]=S[j] 且 S[k]=S[j] 那么最后一定有S[i]=S[k]。因为它们都是必须保证最后相等的。
将必须相等的位置放在一起,相当于连一条边,而位置是点,这些点都是最后必须统一成一个字符的。这样S就被分成好几个连通分量。例如aabd z dfgh就会被分成3组:(a,a,g,h),(b,d,d,f)(z)每一组最终都是必须变成同一个字符。
分好组后就变得很清晰了,只要让每组变成同一个字符,使得变化的字符个数最少即可。那就是总字符数减去最多的那个字符的个数。例如(a,a,g,h)就需要4-2=2个变换,即g,h变成a,a不动就行。
最后将每一组的变换次数加起来就是最终的结果。
代码如下(java版):
package srm589; public class SRM589DV1s250 { private boolean[] visited = new boolean[50]; public int getmin(String S) { int result = 0; for(int i=0;i<S.length();i++){ int[] count = new int[27]; dfs(i,S,count); int total=0; int max=0; for(int j=0;j<count.length;j++){ total+=count[j]; if(max<count[j]) max = count[j]; } result += total-max; } return result; } private void dfs(int k,String S,int[] count){ if(!visited[k]){ visited[k]=true; count[S.charAt(k)-'a']++; for(int i=0;i<S.length();i++){ if(S.charAt(i)==S.charAt(k)||i+k==S.length()-1){ dfs(i,S,count); } } } } public static void main(String[] args) { SRM589DV1s250 srm = new SRM589DV1s250(); System.out.println(srm.getmin("abaabb")); } }
补充:综合编程 , 其他综合 ,