滚动数组应用:POJ 1159
POJ 1159题意:回文词是一种对称的字符串。任意给定一个字符串，通过插入若干字符，都可以变成回文词。现在的任务是，求出将给定字符串变成回文词所需要插入的最少字符数。比如:“Ab3bd”插入2个字符后可以变成回文词“dAb3bAd”或“Adb3bdA”，但是插入少于2个的字符无法变成回文词。
[输入]:
第一行:字符串的长度N(3 <= N <= 5000)
第二行:需变成回文词的字符串
[输出]：
将给定字符串变成回文词所需要插入的最少字符数
[样例]:
Sample Input
5
Ab3bd
Sample Output
2
分析：
S和S' (注:S'是S的反串)的最长公共子串其实一定是回文的。这样我们就可以借助lcs来解决该题，即用s的长度减去lcs的值即可。
import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception{ BufferedReader in = new BufferedReader(new InputStreamReader (System.in)); int total = Integer.parseInt(in.readLine()); String string = in.readLine(); System.out.println(total-LCS(string,new StringBuffer(string).reverse().toString())); } //返回两个string的lcs的长度 public static int LCS(String str1,String str2){ short length1 = (short)str1.length(); short length2 = (short)str2.length(); short[][]result = new short ; //滚动数组,节省空间 for(int i=1;i<=length1;i++){ for(int j=1;j<=length2;j++){ if(str1.charAt(i-1)==str2.charAt(j-1)) result = (short)(result[(i-1)%2]+1); else result = result[(i-1)%2]>result?result[(i-1)%2]:result; } } return result; } }
源码:
页:
[1]