[HIHO1149]回文字符序列（dp）

题目链接：http://hihocoder.com/problemset/problem/1149

题意：中文的。

dp(i,j)表示[i,j]区间内的回文串数量。

如果s[i]!=s[j]，dp(i,j)=dp(i+1,j)+dp(i,j-1)-dp(i+1,j-1)

如果s[i]==s[j]，dp(i,j)=dp(i+1,j)+dp(i,j-1)+1

注意取模

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1010;
const int mod = 100007;
int n;
char s[maxn];
int dp[maxn][maxn];

int main() {
  //freopen("in", "r", stdin);
  int T, _ = 1;
  scanf("%d", &T);
  while(T--) {
    scanf("%s", s); n = strlen(s);
    memset(dp, 0, sizeof(dp));
    for(int i = 0; i < n; i++) dp[i][i] = 1;
    for(int i = 0; i < n; i++) {
      for(int j = i-1; j >= 0; j--) {
        if(s[i] != s[j]) dp[j][i] = dp[j+1][i] + (dp[j][i-1] - dp[j+1][i-1] + mod) % mod;
        else dp[j][i] = dp[j+1][i] + dp[j][i-1] % mod + 1 % mod;
      }
    }
    printf("Case #%d: %d
", _++, dp[0][n-1] % mod);
  }
  return 0;
}