首页 > 其他 > 详细

uva 11584 - Partitioning by Palindromes(dp)

时间:2014-02-25 20:10:24      阅读:271      评论:0      收藏:0      [点我收藏+]

题目链接:uva 11584 - Partitioning by Palindromes


题目大意:给出一个字符串,问说最少可以划分成几个回文串。


解题思路:dp[i]表示从1到第i个字符最少可以划分为几个回文,dp[i] = min{dp[j-1]+1 | judge(j,i) } ,judge函数判断从j到i是否可以形成回文串。


#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;
const int N = 1005;
const int INF = 0x3f3f3f3f;

int n, dp[N];
char str[N];

bool judge(int l, int r) {
	while (l <= r) {
		if (str[l] != str[r]) return false;
		l++; r--;
	}
	return true;
}

int solve () {
	memset(dp, INF, sizeof(dp));
	dp[0] = 0;

	scanf("%s", str+1);
	n = strlen(str+1);

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			if (judge(j, i))
				dp[i] = min(dp[i], dp[j-1]+1);
		}
	}
	return dp[n];
}

int main () {
	int cas;
	scanf("%d", &cas);
	while (cas--) {
		printf("%d\n", solve());
	}
	return 0;
}


uva 11584 - Partitioning by Palindromes(dp)

原文:http://blog.csdn.net/keshuai19940722/article/details/19850441

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!