题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=1513
Palindrome
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4532 Accepted Submission(s): 1547
As an example, by inserting 2 characters, the string "Ab3bd" can be transformed into a palindrome ("dAb3bAd" or "Adb3bdA"). However, inserting fewer than 2 characters does not produce a palindrome.
Ab3bd
题意:给出一个字符串,问要将这个字符串变成回文串要添加最少几个字符
思路:将该字符串与其反转求一次LCS,然后所求就是n减去最长公共子串的长度,但是要注意这里字符串最长有5000,dp数组二维都开5000的话就会超内存,这里就用到了滚动数组,因为在LCS的计算中,i的变化只相差1,所以可以通过对2取余来进行滚动
LCS: 求连个串s1,s2的最长公共自序列:dp[i][j] 表示扫描到第一个串的第i个位置第二个串的第j个位置的最长公共子序列。 当s1[i]==s2[j]时,dp[i][j] = d[i-1][j-1]+1;
当s1[i]!=s2[j]时,dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
空间优化: 通过上面的转移方程可以看出来dp[i][j]的状态之和上一列和当前列有关系,所以可以通过二维滚动数组的形式来储存,通过i的奇偶来控制
下面是代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = ;
char s1[N],s2[N];
int dp[][N];
int n; void LCS()
{
int i,j;
memset(dp,,sizeof(dp));
for(i = ; i<=n; i++)
{
for(j = ; j<=n; j++)
{
int x = i%;
int y = -x;
if(s1[i-]==s2[j-])
dp[x][j] = dp[y][j-]+;
else
dp[x][j] = max(dp[y][j],dp[x][j-]);
}
}
}
int main()
{
int i,j;
while(~scanf("%d",&n))
{
getchar();
scanf("%s",s1);
for(i = ; i < n; i++)
s2[i] = s1[n--i];
//s2[i] = '\0';
LCS();
printf("%d\n",n-dp[n%][n]);
}
return ;
}