UVA 10617 Again Palindrome
做题感悟：这题自己开始按照矩阵连乘的思路画了一个表然后就找到规律了
。
解题思路：首先我们设 dp[ i ] [ j ] 为 从i 到 j 最多有多少回文串。s[ i ] 与s[ j ] 相等或者不相等，
(1)、如果s[ i ] != s[ j ] ,那么如果去掉第 j 个字符回文数为 dp [ i ] [ j-1] ,如果去掉第 i 个字符回文数为dp [ i +1 ] [ j ] ,但是这样重复了区间 i+1 ,j -1 ,so~> dp [ i ] [ j ] = dp [ i ] [ j-1 ] + dp [ i+1 ] [ j ] - dp [ i+1
] [ j-1 ] ;
(2)、如果s [ i ] == s [ j ] ,同理那么如果去掉第 j 个字符回文数为 dp [ i ] [ j-1] ,如果去掉第 i 个字符回文数为dp [ i +1 ] [ j ] ,还得减去 dp [ i+1 ] [ j - 1 ] ,但是 s[ i ] 与 s [ j ] 都不减去也可以那样的话就是 dp [ i+1 ] [ j-1 ] +1 ,
so~> dp [ i ] [ j ] = dp [ i ] [ j - 1 ] + dp[ i + 1 ] [ j ] +1 ;
注意：这题要用long long 。
代码：
#include<stdio.h>
#include<iomanip>
#include<vector>
#include<queue>
#include<fstream>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#define INT long long int
using namespace std ;
const double INF = 99999999 ;
const int MY = 15 ;
const int MX = 100 + 10 ;
INT len ;
char s[MX] ;
INT dp[MX][MX] ;
void init()
{
memset(dp,0,sizeof(dp)) ;
for(INT i=1 ;i<=len ;i++)
dp[i][i]=1 ;
}
void DP()
{
for(INT t=2 ;t<=len ;t++)
for(INT i=1 ;i+t-1<=len ;i++)
{
INT j=i+t-1 ;
if(s[i]==s[j])
dp[i][j]=dp[i][j-1]+dp[i+1][j]+1 ;
else dp[i][j]=dp[i][j-1]+dp[i+1][j]-dp[i+1][j-1] ;
}
cout<<dp[1][len]<<endl ;
}
int main()
{
INT Tx ;
scanf("%lld",&Tx) ;
while(Tx--)
{
scanf("%s",s+1) ;
len=strlen(s+1) ;
init() ;
DP() ;
}
return 0 ;
}
10739 - String to Palindrome
做题感悟：这题也是按照矩阵连乘的思路写的，但是开始写的代码有点挫，不好理解，其实这种题递推一下就好。
解题思路：设 dp[ i ] [ j ] 为 i 到 j 的构成回文的最好操作数。因为删除一个字符和添加一个字符一样的性质，因此看成一种操作。
(1)、如果 s [ i ] == s[ j ] dp [ i ] [ j ] = dp [ i+1 ] [ j - 1 ] ;
(2) 、如果s[ i ] ! = s [ j ] 删除第 i 个字符为 dp [ i+1 ] [ j ] ,删除第 j 个dp [ i ] [ j - 1 ] ,修改第 j 个字符使 s [ i ] = s[ j ] , so ~> dp [ i ] [ j ] = min( dp[ i ][ j-1 ] , min( dp[ i + 1 ][ j ],dp[
i+1 ][ j-1 ] ) ) + 1 ;
代码：
#include<stdio.h>
#include<iomanip>
#include<vector>
#include<queue>
#include<fstream>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#define INT long long int
using namespace std ;
const double INF = 99999999 ;
const int MY = 15 ;
const int MX = 1000 + 10 ;
int Tx,len ;
char s[MX] ;
int dp[MX][MX] ;
void DP()
{
memset(dp,0,sizeof(dp)) ;
for(int t=2 ;t<=len ;t++) // 区间个数
for(int i=1 ;i+t-1<=len ;i++) // 枚举所有区间
{
int j=i+t-1 ;
if(s[i]==s[j]) // 两个字符相等
dp[i][j] =dp[i+1][j-1] ;
else // 不相等
dp[i][j] = min(dp[i][j-1],min(dp[i+1][j],dp[i+1][j-1]))+1 ;
// 分别代表删除第 j 个字符 ，删除第 i 个字符 ，修改第 j 个字符
}
}
int main()
{
int Tx,cse=1 ;
scanf("%d",&Tx) ;
while(Tx--)
{
scanf("%s",s+1) ;
len = strlen(s+1) ;
DP() ;
cout<<"Case "<<cse++<<": "<<dp[1][len]<<endl ;
}
return 0 ;
}
11151 Longest Palindrome
做题感悟：这题挺有意思，早上想了好久都没有AC，下午头脑一热一写代码就Ac了。
解题思路：设 dp [ i ] [ j ] 为字符串 i 到 j 最长的回文串为多长，当然dp[ i ] [ i ] 为 1 ，如果 s[ i ] ==s [ j ] 是 dp[ i ] [ j ] = dp [ i+1 ] [ j -1 ] + 2 ,如果不相等那么dp[ i ] [ j ] = max( dp [ i ][ j-1 ] ,dp [ i+1 ] [ j ]) ;
代码：
#include<stdio.h>
#include<iomanip>
#include<vector>
#include<queue>
#include<fstream>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#define INT long long int
using namespace std ;
const int INF = 99999999 ;
const int MY = 15 ;
const int MX = 1000 + 10 ;
int len ;
char s[MX] ;
int dp[MX][MX],n ;
void DP()
{
memset(dp,0,sizeof(dp)) ;
for(int i=0 ;i<len ;i++)
dp[i][i]=1 ;
for(int t=2 ;t<=len ;t++)
for(int i=0 ;i+t-1<len ;i++)
{
int j=i+t-1 ;
if(s[i]==s[j])
dp[i][j]=dp[i+1][j-1]+2 ;
else dp[i][j]=max(dp[i][j-1],dp[i+1][j]) ;
}
cout<<dp[0][len-1]<<endl ;
}
int main()
{
int Tx ;
scanf("%d",&Tx) ;
getchar() ;
while(Tx--)
{
gets(s) ;
len=strlen(s) ;
DP() ;
}
return 0 ;
}
做题感悟：开始做时还感觉打印字符串不好打印，其实做起来就简单了。
解题思路：这题动态方程不在解释直接给出。
(1) s[ i ] == s[ j ] dp [ i ] [ j ] = dp [ i+1 ] [ j-1 ] ;
(2) s[ i ] != s[ j ] dp[ i ] [ j ] = min { dp [ i+1 ] [ j ] , dp [ i ] [ j-1 ] } +1 ;
关于输出的解释：递归打印路径 --->如果 s [ i ] == s[ j ] 则先输出 s[ i ] 的值（因为 s[ i ] 在左边先输出），然后调用 print( i+1, j-1 ) ,在此语句的后面输出 s [
[ j ]( 当调用完上面的语句后才输出它，因为它在最右边，输出是安从左往右输出的)，否则判断 dp[ i+1 ] [ j ] 与 dp [ i ] [ j - 1 ] 的大小，也就是动态方程的第二种情况，如果是dp [ i +1 ] [ j ] < dp [ i ] [ j - 1 ] ,那么说明当时选择的是 dp [ i +1 ] [ j ] ，添加了s [ i ] 字符到 j 的后面，我们就可以先输出 s [ i ] ,然后调用 print( i+1 , j ) ,输出 s [ i ] (此为添加上的字符)，如果dp
[ i+1 ] [ j ] >= dp[ i ] [ j - 1 ] ,同理输出即可。
代码：
#include<stdio.h>
#include<iomanip>
#include<vector>
#include<queue>
#include<fstream>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#define INT long long int
using namespace std ;
const int INF = 99999999 ;
const int MY = 15 ;
const int MX = 1000 + 10 ;
int n,num ;
char s[MX] ;
int dp[MX][MX] ;
void DP()
{
memset(dp,0,sizeof(dp)) ;
for(int t=2 ;t<=n ;t++)
for(int i=0 ;i+t-1<n ;i++)
{
int j=i+t-1 ;
if(s[i]==s[j])
dp[i][j]=dp[i+1][j-1] ;
else
dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1 ;
}
cout<<dp[0][n-1]<<" " ;
}
void print(int x,int y) // 递归输出
{
if(x==y)
{
cout<<s[x] ;
return ;
}
if(x+1==y&&(s[x]==s[y]))
{
cout<<s[x]<<s[y] ;
return ;
}
if(s[x]!=s[y]) // 说明变化了
{
if(dp[x+1][y]>dp[x][y-1]) // x 前
{
cout<<s[y] ;
print(x,y-1) ;
cout<<s[y] ;
}
else // y+1 前
{
cout<<s[x] ;
print(x+1,y) ;
cout<<s[x] ;
}
}
else
{
cout<<s[x] ;
print(x+1,y-1) ;
cout<<s[y] ;
}
}
int main()
{
while(cin>>s)
{
n=strlen(s) ;
DP() ;
print(0,n-1) ;
cout<<endl ;
}
return 0 ;
}