| Description |
| Leyni喜欢机器人，这次，他得到了一个机器人，这个机器人能接受两种命令，"T"（向后转），"F"（前进一步）。 他还得到了一个用于控制这个机器人的指令序列，他计划恰好修改k次这个指令序列（一次只能修改其中一个指令，同一个指令也可以被反复修改）后让机器人去执行，并使这个机器人最终停下的位置离起点尽量远。 他想知道这个机器人最终停下的位置离起点的最远距离，请你帮助他！ |
| Input |
| 本题有多组测试数据，输入的第一行是一个整数T代表着测试数据的数量，接下来是T组测试数据。 对于每组测试数据： 第1行 包含一个长度不超过100的仅由"T"，"F"组成的非空字符串s代表着原始指令序列。 第2行 包含一个整数k (1 ≤ k ≤ 50)代表着Leyni计划恰好修好这个指令序列的次数。 |
| Output |
| 对于每组测试数据： 第1行 输出这个机器人最终停下的位置离起点的最远距离。 |
| Sample Input |
| 1 TF 1 |
| Sample Output |
| 2 |
CODE:
当前指令为前进时 ：
a[i][j][k]=max(a[i][j][k],a[i-1][j-L][k]+(k?-1:1)); b[i][j][k]=min(b[i][j][k],b[i-1][j-L][k]+(k?-1:1)); 当前指令为转身时 ： a[i][j][k]=max(a[i][j][k],a[i-1][j-L][!k]); b[i][j][k]=min(b[i][j][k],b[i-1][j-L][!k]);
View Code #include#include #define max(a,b)(a)>(b)?(a):(b)#define min(a,b)(a)<(b)?(a):(b)int abs(int x){ return x>0?x:-x;}int a[103][55][2];int b[103][55][2];int main(){ char s[104]; int i,k,j,len,t,K,res,res1,res2,res3,res4; scanf("%d",&t); while(t--) { scanf("%s",s); scanf("%d",&K); len=strlen(s); memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); for(i=0;i<=K;i++) { if((s[0]=='F'&&i%2==0)||(s[0]=='T'&&i%2!=0)){ a[1][i][0]=1; a[1][i][1]=-1; b[1][i][0]=1; b[1][i][1]=-1; } } for(i=2;i<=len;i++) { if(s[i-1]=='F') { a[i][0][0]=a[i-1][0][0]+1; a[i][0][1]=a[i-1][0][1]-1; b[i][0][0]=b[i-1][0][0]+1; b[i][0][1]=b[i-1][0][1]-1; for(k=1;k<=K;k++) { res1=a[i-1][k][0]+1; res2=a[i-1][k][1]-1; res3=b[i-1][k][0]+1; res4=b[i-1][k][1]-1; for(j=0;j<=k;j++) { if(j&1) { res1=max(res1,a[i-1][k-j][1]); res2=max(res2,a[i-1][k-j][0]); res3=min(res3,b[i-1][k-j][1]); res4=min(res4,b[i-1][k-j][0]); } else { res1=max(res1,a[i-1][k-j][0]+1); res2=max(res2,a[i-1][k-j][1]-1); res3=min(res3,b[i-1][k-j][0]+1); res4=min(res4,b[i-1][k-j][1]-1); } } a[i][k][0]=res1; a[i][k][1]=res2; b[i][k][0]=res3; b[i][k][1]=res4; } } else { a[i][0][0]=a[i-1][0][1]; a[i][0][1]=a[i-1][0][0]; b[i][0][0]=b[i-1][0][1]; b[i][0][1]=b[i-1][0][0]; for(k=1;k<=K;k++) { res1=a[i-1][k][1]; res2=a[i-1][k][0]; res3=b[i-1][k][1]; res4=b[i-1][k][0]; for(j=0;j<=k;j++) { if(j&1) { res1=max(res1,a[i-1][k-j][0]+1); res2=max(res2,a[i-1][k-j][1]-1); res3=min(res3,b[i-1][k-j][0]+1); res4=min(res4,b[i-1][k-j][1]-1); } else { res1=max(res1,a[i-1][k-j][1]); res2=max(res2,a[i-1][k-j][0]); res3=min(res3,b[i-1][k-j][1]); res4=min(res4,b[i-1][k-j][0]); } } a[i][k][0]=res1; a[i][k][1]=res2; b[i][k][0]=res3; b[i][k][1]=res4; } } } res=0; res=max(a[len][K][0],a[len][K][1]); res=max(res,abs(b[len][K][0])); res=max(res,abs(b[len][K][1])); printf("%d\n",res); } return 0;}