func_code_string: #include <bits/stdc++.h>   #pragma comment(linker,  /STACK:200000000 )   using namespace std;   const int INF = (int)1E8;   const long long INF64 = (long long)1E18;   const double EPS = 1E-9;   const double PI = acos((double)0) * 2;   const int MAXN = 160;   int n, cost[MAXN];   string s;   bool read() {     if (!(cin >> n)) return false;     for (int i = 0; i < int(n); ++i) {       cin >> cost[i + 1];       if (cost[i + 1] == -1) cost[i + 1] = -INF;     }     cin >> s;     return true;   }   int d[MAXN][MAXN][MAXN];   bool u[MAXN][MAXN][MAXN];   int get_d(int l, int r, int len) {     if (l > r) return cost[len];     if (l == r) return max(cost[len] + cost[1], cost[len + 1]);     int& my = d[l][r][len];     bool& myu = u[l][r][len];     if (myu) return my;     myu = true;     my = -INF;     if (len != 0) my = max(my, cost[len] + get_d(l, r, 0));     for (int i = int(l); i < int(r); ++i)       my = max(my, get_d(l, i, 0) + get_d(i + 1, r, len));     for (int i = int(l + 1); i < int(r + 1); ++i)       my = max(my, get_d(i, r, 0) + get_d(l, i - 1, len));     for (int i = int(l); i < int(r + 1); ++i)       my = max(my, get_d(l, i - 1, 0) + cost[len + 1] + get_d(i + 1, r, 0));     if (s[l] == s[r]) my = max(my, get_d(l + 1, r - 1, len + 2));     return my;   }   int d2[MAXN];   void solve() {     memset(u, 0, sizeof u);     int x = get_d(0, n - 1, 0);     for (int i = 0; i < int(n); ++i) {       d2[i] = i ? d2[i - 1] : 0;       for (int j = 0; j < int(i + 1); ++j)         d2[i] = max(d2[i], get_d(j, i, 0) + (j ? d2[j - 1] : 0));     }     cout << d2[n - 1] << endl;   }   int main() {     if (!read()) throw;     solve();   }   