Codeforces Beta Round #96 (Div. 二)【完整题解】

Codeforces Beta Round #96 (Div. 2)【完整题解】
KIDx 的解题报告
题目链接：http://codeforces.com/contest/133
以下省略头文件，前三题是水题，不解释

A题

如图所示：
如果有循环节：
那么k必然>=times，观察可知：原来的模拟k次，其实相当于模拟：(times - loop + (k-times) % loop)次
#define inf 0x3fffffff#define M 105#define N 55int f[M][N][2], g[M][N][2], d[2] = {1, -1}, tp, k2, i, j, k, num;char s[M];          //d[1] = -1，说明向后走1步，也就是向前走-1步void dp (int f[][N][2], int key){tp = f[i][j][k], k2 = k;if (num & 1)    //变奇数次，s[i]肯定变成另一个字符{if (s[i] == 'T') tp += d[k];    //变成f，所以向前状态k方向走else k2 = !k;    //变成T，下一状态的方向k2变向}else    //s[i]不变{if (s[i] == 'T') k2 = !k;    //k2换向else tp += d[k];    //向k方向走}if (key)f[i+1][j+num][k2] = max (f[i+1][j+num][k2], tp);else f[i+1][j+num][k2] = min (f[i+1][j+num][k2], tp);}int main(){int n, len;while (~scanf ("%s", s)){len = strlen (s);scanf ("%d", &n);for (i = 0; i < M; i++)for (j = 0; j < N; j++)f[i][j][0] = f[i][j][1] = -inf,g[i][j][0] = g[i][j][1] = inf;f[0][0][0] = f[0][0][1] = g[0][0][0] = g[0][0][1] = 0;for (i = 0; i < len; i++)for (j = 0; j <= n; j++)for (k = 0; k < 2; k++)for (num = 0; j + num <= n; num++)  //num表示让当前字符变多少次{if (f[i][j][k] > -inf) dp (f, 1); //对f进行dpif (g[i][j][k] < inf) dp (g, 0); //对g进行dp}printf ("%d\n",max (f[len][n][0],max (f[len][n][1],max (-g[len][n][0], -g[len][n][1]))));}return 0;}