`
128kj
  • 浏览: 600094 次
  • 来自: ...
社区版块
存档分类
最新评论

滚动数组应用: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 [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];   
 }   
       
  
}  


源码:
0
5
分享到:
评论

相关推荐

    树状数组练习:POJ 2481(JAVA)

    【描述】虽然描述部分为空,但我们可以推测,作者在博客中可能详细解释了树状数组的概念、特性以及其在解决实际问题中的应用。通常,这样的文章会包含以下几个方面: 1. **树状数组定义**:树状数组是一种高效的...

    树状数组练习:POJ 3067

    在这个问题中,我们通过分析POJ 3067的题目来探讨如何应用树状数组解决实际问题。 POJ 3067题目大致是这样的:给定一个数组,我们需要在数组上进行一系列的查询和修改操作。查询操作询问区间内元素之和,而修改操作...

    POJ1159-Palindrome

    【标题】"POJ1159-Palindrome" 是北京大学在线编程平台POJ上的一道编程题目。这道题目主要考察的是字符串处理和回文判断的知识点。 【描述】"北大POJ1159-Palindrome 解题报告+AC代码" 暗示了解决这道问题的方法和...

    大顶堆应用:POJ2010

    标题“大顶堆应用:POJ2010”指的是一个关于大顶堆算法在解决实际问题中的应用,特别是针对编程竞赛网站POJ(Programming Online Judge)上的问题2010。大顶堆是一种特殊的完全二叉树,其每个节点的值都大于或等于其...

    北大POJ1159-Palindrome

    北大POJ1159-Palindrome

    ACMer需要掌握的算法讲解 (2).docx

    * 并查集的高级应用:POJ1703、POJ2492 * KMP算法:POJ1961、POJ2406 * 左偏树(可合并堆) 四、搜索 * 最优化剪枝和可行性剪枝 * 较为复杂的动态规划:POJ1191、POJ1054、POJ3280、POJ2029、POJ2948、POJ1925、...

    poj_2682(3).rar_C++ 数组扩充_poj 26_poj 2682_poj26

    "C++ 数组扩充"提示我们问题可能与如何在C++编程语言中处理数组的增长有关,而"poj 26_poj 2682_poj26"似乎是重复提及问题编号,可能是用户在整理文件时的习惯。 描述中提到的“数链思想”可能是指一种处理数组元素...

    凸包练习: POJ 2187(JAVA)

    总结起来,"凸包练习: POJ 2187(JAVA)"是一个关于几何算法的实际应用问题,通过解决这个问题,你可以学习到如何用JAVA编程语言处理几何问题,掌握凸包算法,以及如何有效地读取、处理和输出数据。同时,这也是提升...

    ACM 题型

    - 示例题目:poj1191, poj1054, poj3280, poj2029, poj2948, poj1925, poj3034 2. **四边形不等式** - 示例题目:POJ3254, poj2411, poj1185 3. **记忆化搜索** - 示例题目:poj2057, poj1947, poj2486, poj...

    ACM常用算法及其相应的练习题 (2).docx

    (1) C++的标准模版库的应用:poj3096, poj3007 (2) 较为复杂的模拟题的训练:poj3393, poj1472, poj3371, poj1027, poj2706 (3) 差分约束系统的建立和求解:poj1201, poj2983 (4) 最小费用最大流:poj2516, poj2516,...

    大(小)顶堆练习:POJ 1442

    标题 "大(小)顶堆练习:POJ 1442" 提示我们这是一个关于数据结构和算法的练习题目,特别关注大顶堆或小顶堆的应用。在计算机科学中,大顶堆和小顶堆是两种特殊的二叉堆,它们分别保证了根节点是其子树中最大或最小...

    ACM常用算法及其相应的练习题.docx

    * 最长公共子序列:poj3176, poj1080, poj1159 * 最优二分检索树问题 六、数学 * 组合数学: + 加法原理和乘法原理 + 排列组合 + 递推关系 - poj3252, poj1850, poj1019, poj1942 * 数论: + 素数与整除问题...

    堆排序练习:POJ 2388

    由于描述为空,我们可以假设这是一个通用的堆排序应用,主要关注如何实现堆排序算法,以及如何优化代码以满足竞赛中的性能要求。 标签“源码 工具”暗示了讨论的内容可能包括实际的Java代码实现以及可能使用的辅助...

    田忌赛马: POJ 2287(贪心解法)

    POJ(Programming Online Judge)是国内外广受欢迎的在线编程评测系统,其中的2287题正是以"田忌赛马"为背景的算法问题,主要考察选手对贪心策略的理解和应用。 贪心算法是一种在每一步选择中都采取当前状态下最好...

    直接插入排序练习:POJ 2388

    这个练习题目,"POJ 2388",显然是通过编程实现直接插入排序来解决一个特定的问题。在这个问题中,我们需要理解直接插入排序的机制,并能用Java语言编写出高效的代码。 直接插入排序的基本步骤如下: 1. 从第二个...

    POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类

    - **解释**:这一类问题通常涉及基本的数学运算和数学定理的应用。 #### 2. 几何问题 - **例题**:poj1328, poj2109, poj2586 - **解释**:这类题目涉及到几何图形的处理,比如点、线、面等的计算与判断。 #### 3....

    poj题目分类

    * C++的标准模版库的应用:例如 poj3096、poj3007。 * 较为复杂的模拟题的训练:例如 poj3393、poj1472、poj3371、poj1027、poj2706。 2. 图算法: * 差分约束系统的建立和求解:例如 poj1201、poj2983。 * ...

    ACM常用算法及其相应的练习题 (2).pdf

    * C++的标准模版库的应用:C++的标准模版库是指C++语言的标准库,提供了许多有用的算法和数据结构。例题:poj3096、poj3007。 * 较为复杂的模拟题的训练:较为复杂的模拟题是指需要使用多种算法和数据结构来解决的...

    图的深搜+回溯练习题:POJ2197

    标题中的“图的深搜+回溯练习题:POJ2197”是指一个编程题目,主要涉及图论中的深度优先搜索(DFS, Depth First Search)和回溯算法的应用。这个题目来源于在线编程竞赛平台POJ(Problem Online Judge),编号为2197...

Global site tag (gtag.js) - Google Analytics