rt

如下没有考虑最大值与最小值相乘情况的代码 AC 了。

for(int len = 1; len < n; len++)
	for(int l = 1; l+len <= n*2; l++)
		for(int k = l; k < l+len; k++){
			int ans1, ans2;
			if(ch[k+1] == 't')
				ans1 = f1[l][k]+f1[k+1][l+len], ans2 = f2[l][k]+f2[k+1][l+len];
			else
				ans1 = f1[l][k]*f1[k+1][l+len], ans2 = f2[l][k]*f2[k+1][l+len];
			f1[l][l+len] = max(f1[l][l+len], max(ans1, ans2));
			f2[l][l+len] = min(f2[l][l+len], min(ans1, ans2));
		}