HDU 4632 Palindrome subsequence (区间DP)

时间：2023-12-13 17:24:14

题意

给定一个字符串，问有多少个回文子串（两个子串可以一样）。

思路

注意到任意一个回文子序列收尾两个字符一定是相同的，于是可以区间dp，用dp[i][j]表示原字符串中[i,j]位置中出现的回文子序列的个数，有递推关系：
dp[i][j]=dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]  (*)
如果i和j位置出现的字符相同，那么dp[i][j]可以由dp[i+1][j-1]中的子序列加上这两个字符构成回文子序列，也就是
dp[i][j]+=dp[i+1][j-1]，注意边界特判一下就可以了。

嘛。。。发现区间DP也可以利用容斥~妙~

代码

#include

#include

#include

#include

#include

#include

#include

#define MID(x,y) ((x+y)/2)

#define mem(a,b) memset(a,b,sizeof(a))

using namespace std;

int dp[1003][1003];

int main(){

    int t;

    string s;

    scanf("%d", &t);

    for (int ca = 1; ca > s;

        mem(dp, 0);

        for (int i = 0; i

相关文章