做的我很无奈，当时思路很乱，慌乱之中，起了一个想法，可以做，但是需要优化。尼玛，思路跑偏了，自己挖个坑，封榜之后，才从坑里出来，过的队那么多，开始的时候过的那么快，应该就不是用这种扯淡方法做的。
表示很无奈，没有想到简单的递推式，搞了一个MLE+TLE的方法。
最初版本，多了一个for的复杂度，只要标记一下就好，可是在递归了不好处理，让我折腾了老一会，才弄好。
复制代码
int dfs(int l,int r)
{
int i,ans = ;
if(l == r)
return ;
else if(l > r)
return ;
if(dp[l][r])
return dp[l][r];
ans = dfs(l+,r)+;
for(i = l+; i <= r; i ++)
{
if(str[l] == str[i])
ans = (ans + dfs(l+,i-) + )%MOD;
}
dp[l][r] = ans;
return ans;
} 终于在3点多，改成了递推版本。然后MLE了。
复制代码
for(i = ; i < len; i ++)
{
dp[i][i] = ;
sum[i][i][str[i]-'a'] = ;
}
for(i = ; i < len; i ++)
{
for(j = ; j < len-i; j ++)
{
dp[j][i+j] = (dp[j+][i+j] + + sum[j+][i+j][str[j]-'a'])%MOD;
}
for(j = ; j < len; j ++)
{
if(j == ) continue;
k = str[j-]-'a';
if(i+j- == len) break;
if(str[i+j] == str[j-])
sum[j][i+j][k] = (sum[j][i+j-][k] + dp[j][i+j-] + )%MOD;
else
sum[j][i+j][k] = sum[j][i+j-][k];
}
}
printf("Case %d: %d\n",cas++,dp[][len-]); 终于又改了改，A了。改的，我都看不懂这是什么意思了。
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
#define MOD 10007
char str[];
int dp[][],sum[][][];
int sum1[][];
int sum2[][];
int main()
{
int len,t,cas = ,i,j,k;
scanf("%d",&t);
while(t --)
{
scanf("%s",str);
len = strlen(str);
for(i = ; i < len; i ++)
{
for(j = ; j < len; j ++)
dp[i][j] = ;
}
for(i = ; i < len; i ++)
{
for(j = ; j < ; j ++)
sum1[i][j] = sum2[i][j] = ;
}
for(i = ; i < len; i ++)
{
dp[i][i] = ;
sum1[i][str[i]-'a'] = ;
}
for(i = ; i < len; i ++)
{
if(i% == )
{
for(j = ; j < len-i; j ++)
{
dp[j][i+j] = (dp[j+][i+j] + + sum1[j+][str[j]-'a'])%MOD;
}
for(j = ; j < len; j ++)
{
if(j == ) continue;
k = str[j-]-'a';
if(i+j- == len) break;
if(str[i+j] == str[j-])
sum2[j][k] = (sum1[j][k] + dp[j][i+j-] + )%MOD;
else
sum2[j][k] = sum1[j][k];
}
}
else
{
for(j = ; j < len-i; j ++)
{
dp[j][i+j] = (dp[j+][i+j] + + sum2[j+][str[j]-'a'])%MOD;
}
for(j = ; j < len; j ++)
{
if(j == ) continue;
k = str[j-]-'a';
if(i+j- == len) break;
if(str[i+j] == str[j-])
sum1[j][k] = (sum2[j][k] + dp[j][i+j-] + )%MOD;
else
sum1[j][k] = sum2[j][k];
}
}
}
printf("Case %d: %d\n",cas++,dp[][len-]);
}
return ;
}