本文主要是介绍ural Mnemonics and Palindromes （dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.timus.ru/problem.aspx?space=1&num=1635
给出一个字符串，将这个字符串分成尽量少的回文串。
起初没有思路，想着应该先预处理出所有的回文串，然后进行dp。但是字符串的长度是4000，O(n^3)肯定不行，其实可以转化为O(n^2)，就是枚举中点而不是枚举起点和终点，又NC了吧。
然后就是线性的dp了。dp[i]表示到第i位为止最少的回文串数，那么dp[i] = min(dp[i],dp[j+1]+1)，j < i 且i到j也是回文串。
输出路径时用pre数组记录每个得到的回文串的起始位置就行。
#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
#define LL __int64
#define eps 1e-12
#define PI acos(-1.0)
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 4010;char s[maxn];
int tmp[maxn][maxn];
int len;
int dp[maxn],pre[maxn];
int is_p[maxn];void init()
{//枚举中点，求出所有回文串memset(tmp,0,sizeof(tmp));for(int i = 0; i < len; i++){tmp[i][i] = 1;for(int j = 1;; j++) //长度为奇数的回文串{if(i-j < 0 || i+j >= len)break;if(s[i-j] == s[i+j])tmp[i-j][i+j] = 1;else break;}for(int j = 1; ; j++)//长度为偶数的回文串{if(i-j+1 < 0 || i+j >= len)break;if(s[i-j+1] == s[i+j])tmp[i-j+1][i+j] = 1;else break;}}
}int main()
{while(~scanf("%s",s)){len = strlen(s);init();memset(dp,INF,sizeof(dp));memset(pre,-1,sizeof(pre));for(int i = 0; i < len; i++){if(tmp[0][i] == 1){dp[i] = 1;pre[i] = 0;}}for(int i = 0; i < len; i++){if(dp[i] == 1) continue;for(int j = 0; j < i; j++){if(tmp[j+1][i] && dp[i] > dp[j]+1){dp[i] = dp[j]+1;pre[i] = j+1;}}}printf("%d\n",dp[len-1]);memset(is_p,-1,sizeof(is_p));int t = len-1,tt;while(1){if(t < 0)break;tt = pre[t];is_p[tt] = 1;t = tt-1;}for(int i = 0; i < len; i++){if(is_p[i] == 1 && i != 0)printf(" ");printf("%c",s[i]);}printf("\n");}return 0;
}
这篇关于ural Mnemonics and Palindromes （dp）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
