func_code_string: #include <bits/stdc++.h>   using namespace std;   const int MAXN = 150 + 10;   void remax(int& x, int y) {     if (x < y) {       x = y;     }   }   int n;   char s[MAXN];   int a[MAXN];   bool read() {     if (scanf( %d n , &n) < 1) {       return 0;     }     for (int i = 0; i < (int)n; ++i) {       scanf( %d , &a[i + 1]);     }     scanf(  n );     scanf( %s n , s);     assert((int)strlen(s) == n);     return 1;   }   int dp[MAXN][MAXN];   int dp_pal[MAXN][MAXN][MAXN];   int dp_full[MAXN][MAXN];   int solve() {     memset(dp, 0, sizeof dp);     memset(dp_full, -1, sizeof dp_full);     memset(dp_pal, -1, sizeof dp_pal);     for (int len = 1; len <= n; ++len) {       for (int l = 0; l < (int)n - len + 1; ++l) {         int r = l + len - 1;         assert(r < n);         {           for (int m = l; m < r; ++m) {             if (dp_full[l][m] != -1 && dp_full[m + 1][r] != -1) {               remax(dp_full[l][r], dp_full[l][m] + dp_full[m + 1][r]);             }           }           if (s[l] == s[r]) {             if (len <= 2) {               remax(dp_full[l][r], a[len]);             } else {               remax(dp_full[l][r], dp_pal[l + 1][r - 1][2]);             }           }         }         {           for (int m = l; m < r; ++m) {             remax(dp[l][r], dp[l][m] + dp[m + 1][r]);           }           remax(dp[l][r], dp_full[l][r]);         }         {           for (int out = 2; out <= n - len; out += 2) {             if (dp_full[l][r] != -1 && a[out] != -1) {               remax(dp_pal[l][r][out], dp_full[l][r] + a[out]);             }             for (int m = l; m < r; ++m) {               if (dp_pal[l][m][out] != -1 && dp_full[m + 1][r] != -1) {                 remax(dp_pal[l][r][out], dp_pal[l][m][out] + dp_full[m + 1][r]);               }             }             for (int m = l + 1; m <= r; ++m) {               if (dp_full[l][m - 1] != -1 && dp_pal[m][r][out] != -1) {                 remax(dp_pal[l][r][out], dp_full[l][m - 1] + dp_pal[m][r][out]);               }             }             if (s[l] == s[r]) {               if (len <= 2) {                 remax(dp_pal[l][r][out], a[out + len]);               } else {                 remax(dp_pal[l][r][out], dp_pal[l + 1][r - 1][out + 2]);               }             }           }         }       }     }     return dp[0][n - 1];   }   int main() {     while (read()) {       printf( %d n , solve());     }     return 0;   }   