CF1107E Vasya and Binary String

#include <stdio.h>
#include <string.h>
#include <algorithm>
const int N = 105;
typedef long long LL;
int n, tot[N]; // tot表示i右边的同色的个数
char str[N]; LL a[N], f[N][N][N];
int main() {
	scanf("%d%s", &n, str + 1);
	for(int i = 1; i <= n; i ++) scanf("%lld", a + i); // 先更新一下 a
	for(int i = 1; i <= n; i ++) for(int j = 1; j < i; j ++) a[i] = std::max(a[i], a[j] + a[i-j]);
	for(int i = 1; i <= n; i ++) for(int j = i + 1; j <= n; j ++) tot[i] += str[i] == str[j];
	for(int len = 1; len <= n; len ++)
		for(int l = 1, r = len; r <= n; l ++, r ++) {
			for(int t = 0; t <= tot[r]; t ++) {
				f[l][r][t] = f[l][r-1][0] + a[t+1];
				for(int k = l; k < r; k ++) if(str[k] == str[r])
					f[l][r][t] = std::max(f[l][r][t], f[l][k][t+1] + f[k+1][r-1][0]);
			}
		}
	printf("%lld\n", f[1][n][0]);
	return 0;
}