题意：给你一个只包含T（转身） ，F（继续浅见）的序列，问你改变其中的n个值，它离原来坐标最远的距离。
解题思路：只需要记录正向最大最小值，反向最大最小值即可。有点类似于14年湖南省赛那个题目。
解题代码：
1 // File Name: 132c.cpp 2 // Author: darkdream 3 // Created Time: 2015年03月22日 星期日 19时43分45秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 26 using namespace std; 27 char str[1000]; 28 int k; 29 int dp[105][105][2][2]; 30 void update(int &x ,int v,int status) 31 { 32 if(status == 1) 33 { 34 x = max(x,v); 35 return; 36 } 37 x = min(x,v); 38 } 39 int main() 40 { 41 scanf("%s",&str[1]); 42 scanf("%d",&k); 43 int len = strlen(&str[1]); 44 for(int i = 0 ;i <= len; i ++) 45 for(int j = 0 ;j <= k ;j ++) 46 { dp[i][j][1][0] = 1e9; 47 dp[i][j][1][1] = -1e9; 48 dp[i][j][0][0] = 1e9; 49 dp[i][j][0][1] = -1e9; 50 } 51 dp[0][0][1][0] = 0 ; 52 dp[0][0][1][1] = 0 ; 53 for(int i = 1 ; i <= len ; i ++) 54 { 55 int st = 0; 56 if(str[i] == 'F') 57 { 58 for(int j =0 ;j <= k;j ++) 59 { 60 update(dp[i][j][1][0],dp[i-1][j][1][0] +1,0) ; 61 update(dp[i][j][1][1],dp[i-1][j][1][1] +1,1) ; 62 update(dp[i][j][0][0],dp[i-1][j][0][0] -1,0) ; 63 update(dp[i][j][0][1],dp[i-1][j][0][1] -1,1) ; 64 update(dp[i][j+1][1][0],dp[i-1][j][0][0],0); 65 update(dp[i][j+1][1][1],dp[i-1][j][0][1],1); 66 update(dp[i][j+1][0][0],dp[i-1][j][1][0],0); 67 update(dp[i][j+1][0][1],dp[i-1][j][1][1],1); 68 } 69 }else{ 70 for(int j =0 ;j <= k;j ++) 71 { 72 update(dp[i][j+1][1][0],dp[i-1][j][1][0] +1,0) ; 73 update(dp[i][j+1][1][1],dp[i-1][j][1][1] +1,1) ; 74 update(dp[i][j+1][0][0],dp[i-1][j][0][0] -1,0) ; 75 update(dp[i][j+1][0][1],dp[i-1][j][0][1] -1,1) ; 76 update(dp[i][j][1][0],dp[i-1][j][0][0],0); 77 update(dp[i][j][1][1],dp[i-1][j][0][1],1); 78 update(dp[i][j][0][0],dp[i-1][j][1][0],0); 79 update(dp[i][j][0][1],dp[i-1][j][1][1],1); 80 } 81 } 82 for(int j = 2;j <= k;j ++) 83 { 84 update(dp[i][j][1][0],dp[i][j-2][1][0],0); 85 update(dp[i][j][1][1],dp[i][j-2][1][1],1); 86 update(dp[i][j][0][0],dp[i][j-2][0][0],0); 87 update(dp[i][j][0][1],dp[i][j-2][0][1],1); 88 } 89 /*for(int j = 0 ;j <= k;j ++) 90 printf("%d ",dp[i][j][0]); 91 printf(" "); 92 for(int j = 0 ;j <= k;j ++) 93 printf("%d ",dp[i][j][1]); 94 printf(" "); 95 printf("************ ");*/ 96 } 97 int ans = 0; 98 if(abs(dp[len][k][1][0]) <= 100 && abs(dp[len][k][1][0]) > ans) 99 { 100 ans = abs(dp[len][k][1][0]); 101 } 102 if(abs(dp[len][k][1][1]) <= 100 && abs(dp[len][k][1][1]) > ans) 103 { 104 ans = abs(dp[len][k][1][1]); 105 } 106 if(abs(dp[len][k][0][0]) <= 100 && abs(dp[len][k][0][0]) > ans) 107 { 108 ans = abs(dp[len][k][0][0]); 109 } 110 if(abs(dp[len][k][0][1]) <= 100 && abs(dp[len][k][0][1]) > ans) 111 { 112 ans = abs(dp[len][k][0][1]); 113 } 114 printf("%d ",ans); 115 //printf("%d %d %d %d ",dp[len][k][1][0],dp[len][k][1][1],dp[len][k][0][0],dp[len][k][0][1]); 116 117 return 0; 118 }