先说HDU 4632这道题，因为比较简单，题意就是给你一个字符串，然后给你一个区间，叫你输出区间内所有的回文子序列，注意是回文子序列，不是回文字串。
用dp[i][j]表示区间[i,j]内的回文子序列的个数。
那么可以得到状态转移方程：dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1] + a[i] == a[j] .
#define N 1005
#define MOD 10007
int dp[N][N] ;
char a[N] ;
int main（） {
int T ;
cin 》 T ;
int cc = 0;
while（ T -- ）{
cin 》 a ;
int l = strlen（a） ;
mem（dp ,0 ） ;
for （int i = 0 ; i < l ; i ++ ）dp[i][i] = 1 ;
for （int i = 2 ; i <= l ; i ++ ）{//枚举长度
for （int j = 0 ; j + i - 1 < l ; j ++ ）{//枚举起点
int s = j ;
int e = j + i - 1 ;
if（a[s] == a[e]）dp[s][e] ++ ;
else {
if（s + 1 <= e - 1）{
dp[s][e] -= dp[s + 1][e - 1] ;
dp[s][e] = （dp[s][e] + MOD） % MOD ;
}
}
dp[s][e] += （ dp[s + 1][e] + dp[s][e - 1] ） % MOD ;
}
}
printf（"Case %d: ",++cc） ;
cout 《 （dp[0][l - 1] + MOD ） % MOD 《 endl;
}
return 0 ;
}
CF 245H .这道题的题意差不多，不过他是给出区间，求出区间内的回文字串的个数。
上面那道题之所以我认为简单，是因为他不用判断[i , j ]之间是不是回文，因为他只需要计数就可以了。
而这道题，即使a[i] == a[j],也要判断[i + 1 , j - 1]之内是不是回文。
这里我是多开一个数组来存当前区间是否是回文，用isP[i][j]来判断这个区间是否是回文。
初始化isP[i][i] = 1 ,dp[i][i] = 1 ,因为他本身肯定是回文。
当然初始化的时候还要注意isP[i + 1][i] = 1 ,因为我们注意到，当枚举到长度为2的时候，我们假设字符串为aa .
那么首先a[i] == a[j] .然后还要判断[i + 1, j - 1]是否是回文，那么我们注意到，其实i + 1 > j - 1.实际上i + 1 = （j - 1 + 1），但是这个情况其实也是回文。
所以我们要多初始化一位，让isP[i + 1][i] = 1 ,这是对长度为2的字串进行特殊的处理。
明白了这点。那么状态转移方程就很好写了：dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1] + a[i] == a[j] && isP[i + 1][j - 1].
#define N 5005
char a[N] ;
int dp[N][N] ;
int isP[N][N] ;
int main（） {
scanf（"%s",a + 1） ;
int n ;
cin 》 n ;
int l = strlen（a + 1） ;
for （int i = 1 ; i <= l ; i ++ ）dp[i][i] = 1 ,isP[i][i] = 1 , isP[i + 1][i] = 1 ;
for （int i = 2 ; i <= l ; i ++ ） {
for （int j = 1 ; j + i - 1 <= l ; j ++ ） {
int s = j ;
int e = j + i - 1 ;
isP[s][e] = isP[s + 1][e - 1] && a[s] == a[e] ;
dp[s][e] += dp[s + 1][e] + dp[s][e - 1] - dp[s + 1][e - 1] + isP[s][e];
}
}
while（n -- ） {
int aa , bb ;
RD（aa） ;
RD（bb） ;
OT（dp[aa][bb]） ;
puts（""） ;
}
return 0 ;
} |