当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

滚动数组应用:POJ 1159

发表于: 2012-12-29   作者:128kj   来源:转载   浏览:
摘要: POJ 1159题意:    回文词是一种对称的字符串。任意给定一个字符串,通过插入若干字符,都可以变成回文词。现在的任务是,求出将给定字符串变成回文词所需要插入的最少字符数。比如:“Ab3bd”插入2个字符后可以变成回文词“dAb3bAd”或“Adb3bdA”,但是插入少于2个的字符无法变成回文词。 [输入]: 第一行:字符串的长度N(3 <= N <=
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 [2][length2+1];   //滚动数组,节省空间
    
    for(int i=1;i<=length1;i++){   
      for(int j=1;j<=length2;j++){   
        if(str1.charAt(i-1)==str2.charAt(j-1))   
         result[i%2][j] = (short)(result[(i-1)%2][j-1]+1);   
        else  
         result[i%2][j] = result[(i-1)%2][j]>result[i%2][j-1]?result[(i-1)%2][j]:result[i%2][j-1];   
        }   
    }   
    return result[length1%2][length2];   
 }   
       
  
}  


源码:

滚动数组应用:POJ 1159

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
1) 题目 Palindrome Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 46005 Accepted:
滚动数组 code: #include <iostream> using namespace std; int shu[1000005]; int main(int
一个水题。。。结果因为一个加号写成了减号。。。硬是耗费了一个多小时。。。T^T Counting Black Ti
Stars Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 22968 Accepted: 10011 Descri
这道题好像被贱做了,看起来像二维的树状数组,其实只是一维的,可能是数据太大了,矩阵开不那么大
关于树状数组,参看: http://128kj.iteye.com/blog/1743633 POJ3067题意: 东海岸与西海岸分别有N和M
  这题是我看了大白书树状数组后刷的第一道题,确实难度不小,所以只好上网找题解了,网上的做法
  之前说过这是线段树的裸题,但是当看了http://kenby.iteye.com/blog/962159 这篇题解后我简直震
题目来源Ural Collegiate Programming Contest 1999 poj上的链接点这儿(这个是难得的1Y"o((>ω&
Stars Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 20885 Accepted: 9097 Descrip
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号