水题

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #define mod 10007 7 using namespace std; 8 char str[1002]; int dp[1002][1002],cas; 9 void work( )10 {11     int len = strlen( str );12     memset( dp,0,sizeof(dp) );13     for( int i = 0; i < len; i++ )dp[i][i] = 1;14     for( int i = 1; i < len; i++ )15     for( int j = 0; j + i < len; j++ )16     {17         int t = i+j;18           dp[j][t] =  dp[j][t-1] + dp[j+1][t]; if( j+1 <= t-1 ) dp[j][t] -= dp[j+1][t-1];19         if( str[j] == str[t] )20         {21           if(  j+1 <= t-1 ) dp[j][t] +=  dp[j+1][t-1] + 1;22           else  dp[j][t]++;23         }24         dp[j][t] %=  mod; dp[j][t] += mod;25     }26     dp[0][len-1] %= mod;27     printf("Case %d: %d\n",cas++,dp[0][len-1]);28 }29 int main( )30 {31    int T; cas = 1;scanf("%d",&T);32    while( T-- ){33        scanf("%s",&str);work( );34    }35    return 0;36 }