//CF132C
#include <algorithm>
#include <cstring>
#include <cstdio>

const int N = 105;
int n, m, f[N][N*2][N][2]; 
char s[N];

int main(){
	scanf("%s%d", s+1, &m);
	n = strlen(s+1);
	//*******
	f[0][N][0][0] = f[0][N][0][1] = 1;
	//*******
	for(int i = 1; i <= n; ++ i){
		for(int j = 1; j < N*2-1; ++ j){
			for(int k = 0; k <= m; ++ k){
				if(s[i] == 'T'){
					f[i][j][k][0] |= f[i-1][j][k][1];
					f[i][j][k][1] |= f[i-1][j][k][0];
					if(k){
						f[i][j][k][0] |= f[i-1][j-1][k-1][0];
						f[i][j][k][1] |= f[i-1][j+1][k-1][1];
					}
				} else {
					f[i][j][k][0] |= f[i-1][j-1][k][0];
					f[i][j][k][1] |= f[i-1][j+1][k][1];
					if(k){
						f[i][j][k][0] |= f[i-1][j][k-1][1];
						f[i][j][k][1] |= f[i-1][j][k-1][0];
					}
				}
			}
		}
	}
	int ans = 0;
	for(int i = 1; i < N*2-1; ++ i){
		for(int j = m; j >= 0; j -= 2){
			if(f[n][i][j][0] || f[n][i][j][1]){
				ans = std::max(ans, i-N);
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

$f_{i,j,k,l}$ 表示第 $i$ 步走到 $j-N$ 处，改变了 $k$ 个步骤，方向为 $l$ 是否可行。

用星号框起来的那行，为什么要把初始的时候朝着两个方向都设为可行？两个方向不应该是对称的吗？应该只用考虑一个方向就行了啊？

---

只初始化一个方向，错误数据：

Input

TFFTFTTTFFTFTFTTTFFTTFFTFTFFTFFFFTTTTTFTFTFTTFFTTFTFFTTFTFFTTTTFFTFTTTFTTTTFFFFTFFTFFTFFFFTTTT
2

Output

13

Answer

19

---

然后我打了个暴力

#include <cstdio>
#include <cstring>

char s[100], t[100];
int main(){ int ans = 0;
	scanf("%s", s+1);
	int n = strlen(s+1);
	for(int i = 1; i <= n; ++ i){
		for(int j = i+1; j <= n; ++ j){	
			memcpy(t, s, sizeof(s));
			if(t[i] == 'F') t[i] = 'T';
			if(t[i] == 'T') t[i] = 'F';
			if(t[j] == 'F') t[j] = 'T';
			if(t[j] == 'T') t[j] = 'F';
			int pos = 0, to = 1;
			for(int i = 1; i <= n; ++ i){
				if(t[i] == 'T') to *= -1;
				else pos += to;
			}
			if(pos > ans) ans = pos;
		}
	}
	printf("%d\n", ans);
}

发现确实答案应该是 13，这是为什么？