电子龟的行动，是沿着直线左右走动的。他能够接受两种指令，“T”（向后转，即如果面向左，改成向右；否则就向左）和“F”（向当前面朝的方向往前移动一个单位距离）。
现在给出一串指令，让电子龟来执行。你必须改动n次指令，一次改变一个（一个指令可以改动多次）。使得电子龟执行完所有的指令后，离起始点最远。
样例解释：
在第一个样例中，最好方案是把“T”变成“F”，最远距离为2。
在第二个样例中，最好方案是把第四个变成“F”，然后把最后一个或者第一个变成“T”。
输入
单组测试数据 第一行是一个字符串S，代表原始的指令串，只包含'T','F'字符。（1≤|S|≤100） 第二行是一个整数n，表示要对指令作多少次改变。（1≤n≤50）
输出
共一行，一个整数，表示电子龟执行完所有的指令后，离起始点的最远距离。
输入样例
样例输入1
FT
1
样例输入2
FFFTFFF
2
输出样例
样例输出1 2 样例输出2 6
只有两个行走方向，设0表示正方向，1表示反方向。
dp[len][n][d],len是字符下标，n是变换次数，可以对一个字符重复变换，具体怎么变不需要深究，只需要进行状态转换。
dp[i][j][di],如果说第i个字符是'F'，对于j（0~n），他的状态可以用dp[i - 1][j - k][]来更新，k在0~j范围内，也就是说两个状态相差k此变换，变换次数如果是偶数，可以相当于没变，如果是奇数，多出来第一次要么把T变F,要么把F变T，
这里是'F'变'T',方向变了，就要用反方向的来更新，如果k是偶数，就正方向的朝着正方向多走一步，反方向的往回走-1.
如果第i个是'T'，k是奇数，变换此字符，方向相当于不变，k是偶数，方向变反。
代码：
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #define inf 0x3f3f3f3f using namespace std; int n,c,dp[105][55][2]; char s[105]; int main() { scanf("%s %d",s + 1,&n); int len = strlen(s + 1); memset(dp,-inf,sizeof(dp)); dp[0][0][1] = dp[0][0][0] = 0; for(int i = 1;i <= len;i ++) { for(int j = 0;j <= n;j ++) {///修改了j个字符，要么是T->F,要么F->T for(int k = 0;k <= j;k ++) { if(s[i] == 'F' && k & 1 || s[i] == 'T' && !(k & 1)) { dp[i][j][0] = max(dp[i][j][0],dp[i - 1][j - k][1]); dp[i][j][1] = max(dp[i][j][1],dp[i - 1][j - k][0]); } else { dp[i][j][0] = max(dp[i][j][0],dp[i - 1][j - k][0] + 1); dp[i][j][1] = max(dp[i][j][1],dp[i - 1][j - k][1] - 1); } } } } printf("%d",max(dp[len][n][0],dp[len][n][1])); return 0; }