[ARC087D]FT Robot

题目大意：
　　一个机器人按照给定的一系列指令进行运动。
　　总共有两种指令：
　　T：向某个方向旋转90度。
　　F：向当前所朝的方向走一个单位长度。
　　一开始机器人站在原点，且朝向x的正半轴方向，问机器人是否可能会经过点(x,y)。

思路：
　　不难想到一个O(n^3)的DP。
　　考虑如何重新设计状态来优化到O(n^2).
　　显然，横向运动的过程和纵向运动的过程是独立的。
　　我们不妨分开考虑这两种情况。
　　我们可以对于给定的指令序列分组，使得每一组的指令都是若干个F加上一个T的形式（当然也可以没有F）。
　　显然，这时候对于每一组的指令，机器人的运动情况都是向当前方向前进若干步再转弯。
　　而如果我们对每一组指令进行编号，显然，机器人移动的方向与组的编号有关。
　　编号为奇数的在水平方向上移动，反之则在竖直方向上移动。
　　以水平方向为例，用f[i]表示是否可能走到横坐标为i的位置，d[j]表示第j组中F的个数，那么f[i]=f[i-d[j]]||f[i+d[j]]。
　　其中如果第一个指令就是F，就只能往右走而不能往左走，要特判一下。
　　最后就只需要分别判断一下x和y是否可以到达即可。

 #include<cstdio>

 #include<cctype>

 #include<cstring>

 inline int getint() {

     register char ch;

     register bool neg=false;

     while(!isdigit(ch=getchar())) if(ch=='-') neg=true;

     register int x=ch^'';

     while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');

     return neg?-x:x;

 }

 const int N=,M=;

 char s[N];

 int op[N]={};

 bool f[][M],tmp[M];

 int main() {

     scanf("%s",s);

     const int x=getint(),y=getint();

     op[]=s[]=='F';

     for(register int i=;s[i];i++) {

         if(s[i]=='T'&&s[i-]=='T') op[++op[]]=;

         if(s[i]=='F') {

             if(s[i-]=='T') op[]++;

             op[op[]]++;

         }

     }

     f[][N]=f[][N]=true;

     for(register int i=;i<=op[];i++) {

         memset(tmp,,sizeof tmp);

         for(register int j=;j<M-op[i];j++) tmp[j+op[i]]|=f[i&][j];

         if(i!=) for(register int j=op[i];j<M;j++) tmp[j-op[i]]|=f[i&][j];

         memcpy(f[i&],tmp,sizeof tmp);

     }

     puts(f[][N+y]&&f[][N+x]?"Yes":"No");

     return ;

 }