【51nod 1154】回文串划分

有一个字符串S，求S最少可以被划分为多少个回文串。

例如：abbaabaa，有多种划分方式。

a|bb|aabaa - 3 个回文串

a|bb|a|aba|a - 5 个回文串

a|b|b|a|a|b|a|a - 8 个回文串

其中第1种划分方式的划分数量最少。

Input

输入字符串S(S的长度<= 5000)。

Output

输出最少的划分数量。

Input示例

abbaabaa

Output示例

题解

设dp[i]为考虑（i~len）的最少分割，那么

\(dp[i]=min(dp[i],dp[j+1]+1)\;if(i,j)为回文串\)

这个可以倒推也可以正推，至于求回文串

if a[i]==a[j] and (i-1,j+1)是回文串

then (i,j)是回文串，这个是\(O(n^2)\)，与dp方程同级，就放在一起转移吧。

参考代码

import java.io.*;

import java.util.*;

public class Main {

	static final int N=(int)5005;

	static int dp[]=new int[N];

	static char a[]=new char[N];

	static boolean p[][]=new boolean[N][N];

    public static void main(String[] args) {

        InputStream sys=System.in;

        InputReader in=new InputReader(sys);

        PrintWriter out=new PrintWriter(System.out);

        a=in.next().toCharArray();

        dp[a.length]=0;

        for(int i=a.length-1;i>=0;i--) {

        	dp[i]=Integer.MAX_VALUE;

        	for(int j=i;j<=a.length-1;j++) {

        	     if(a[i]==a[j]&&(j-i<2||p[i+1][j-1])) {

        	    	 p[i][j]=true;

        	    	 dp[i]=Math.min(dp[i], dp[j+1]+1);

        	     }

        	}

        }

        out.println(dp[0]);

	    out.flush();

    }

	static class InputReader {

		public BufferedReader reader;

		public StringTokenizer tokenizer;

		public InputReader(InputStream stream) {

			reader = new BufferedReader(new InputStreamReader(stream), 32768);

			tokenizer = null;

		}

		public String next() {

			while (tokenizer == null || !tokenizer.hasMoreTokens()) {

				try {

					tokenizer = new StringTokenizer(reader.readLine());

				} catch (IOException e) {

					throw new RuntimeException(e);

				}

			}

			return tokenizer.nextToken();

		}

		public int nextInt() {

			return Integer.parseInt(next());

		}

	}

}

巴特西

【51nod 1154】回文串划分

Input

Output

Input示例

Output示例

题解

参考代码

最新文章

热门文章

巴特西

【51nod 1154】 回文串划分

Input

Output

Input示例

Output示例

题解

参考代码

最新文章

热门文章

【51nod 1154】回文串划分