HDU 4632 Palindrome subsequence 还有一些遗留问题

思路提供在第一次代码中。
使用char[],strlen(),\(Accepted\)

/* 区间 DP 
 * 用较短区间的值算出较长区间的值
*/
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int mod = 10007;

char str[1005];
int T, len;
int dp[1005][1005] = {};

int main () {
  scanf("%d", &T);
  for (int times = 1; times <= T; times++) {
    scanf("%s", str);
    len = strlen(str);

    for (int i = 0; i < len; i++) dp[i][i] = 1; // 单独一个字符是一个回文序列

    for (int i = 1; i < len; i++)
      for (int j = i-1; j >= 0; j--) {
        // j~i的回文数是 j~i-1的回文数加 j+1~i的回文数，减去 j+1~i-1的回文数
        dp[j][i] = (dp[j+1][i] + dp[j][i-1] - dp[j+1][i-1] + mod) % mod;
        
        // 两边相等则两边组成一个回文序列，且可以和中间每一个回文序列构成新序列
        if (str[i] == str[j])
          dp[j][i] = (dp[j][i] + dp[j+1][i-1] + 1) % mod;
      }

    printf("Case %d: %d\n", times, dp[0][len-1]);
  }

  return 0;
}

使用string,cin,\(Accecped\)

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int mod = 10007;

string str;
int T, len;
int dp[1005][1005] = {};

int main () {
  scanf("%d", &T);
  for (int times = 1; times <= T; times++) {
    cin >> str;
    len = str.length();

    for (int i = 0; i < len; i++) dp[i][i] = 1;

    for (int i = 1; i < len; i++)
      for (int j = i-1; j >= 0; j--) {
        dp[j][i] = (dp[j+1][i] + dp[j][i-1] - dp[j+1][i-1] + mod) % mod;
        
        if (str[i] == str[j])
          dp[j][i] = (dp[j][i] + dp[j+1][i-1] + 1) % mod;
      }

    printf("Case %d: %d\n", times, dp[0][len-1]);
  }

  return 0;
}

使用string,strlen(),及string.c_str(),\(Wrong Answer\)

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int mod = 10007;

string s;
int T, len;
int dp[1005][1005] = {};

int main () {
  scanf("%d", &T);
  for (int times = 1; times <= T; times++) {
    scanf("%s", s.c_str());
    len = strlen(s.c_str());

    for (int i = 0; i < len; i++) dp[i][i] = 1;

    for (int i = 1; i < len; i++)
      for (int j = i-1; j >= 0; j--) {
        dp[j][i] = (dp[j+1][i] + dp[j][i-1] - dp[j+1][i-1] + mod) % mod;
        
        if (s[i] == s[j])
          dp[j][i] = (dp[j][i] + dp[j+1][i-1] + 1) % mod;
      }

    printf("Case %d: %d\n", times, dp[0][len-1]);
  }

  return 0;
}

在做HDU 1181时也用了string.c_str()，但当时没意识到使这里的问题。
在本地对拍一直找不到问题。

HDU 4632 Palindrome subsequence 还有一些遗留问题

原文：https://www.cnblogs.com/Vty66CCFF/p/12718077.html