2015年大连邀请赛F题

我昨天晚上才知道原来四省赛的题目可以在NEU OJ上提交，附上网址 http://acm.neu.edu.cn/hustoj/

这道题现场做的时候被我想复杂了，我已开始把这道题当做贪心+dp来做了，搞了一个三维的dp方程，复杂度是o(10^9)。当时的想法是，最优的一定是把T变成F，然后如果连续的F或T的话，那么先把他们合并成一堆，这样每次能在这堆中走的长度就已知了，然后再把T组成的一堆，如果是奇数，那么我们就留下一个，如果是偶数，那么就直接扔掉这一堆，再把相邻的两个F堆合并成一对。。。然后最终的形式就是有n个F堆，每两个堆之间用一个T隔开来，求最长路，这个样子一个三维dp就出来了，算下复杂度，然后找优化，结果就一直跪在这里了。。。

后来听了裁判的讲解，尼玛。。。这么水。其实一开始就搞错了，直接在原序列上进行操作就好了（强行要分堆，增加游戏难度）。

下面写一下dp方程：

dp[i][j][k]：i代表前i个命令，j代表改变了j次，k = 0代表向右走的最长路，k = 1代表向左做的最长路，

dp[i][j][0] = max(dp[i-1][j][0] + (执行第i个命令走出的步数(-1,0,1)，具体怎么搞可以看代码),dp[i-1][j-1][0])+ (执行第i个命令走出的步数(-1,0,1)，具体怎么搞可以看代码));

同理dp[i][j][1]。

注意一下边界条件，这道题马上就可以ac了。

下面附上ac代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#define ll  long long
#define FOR(i,x,y)  for(int i = x;i < y;i ++)
#define IFOR(i,x,y) for(int i = x;i > y;i --)

using namespace std;

const int M = 1005;
const int N = 505;
int dp[M][N][2],mat[M],n,m;
char str[M];

int dir(int i,int j){
    return (mat[i] + j) % 2;
}

int main()
{
    //freopen("test.in","r",stdin);
    int t,tCase = 0;
    scanf("%d",&t);
    while(t--){
        scanf("%s%d",str,&m);
        n = strlen(str);
        mat[0] = 0;
        FOR(i,1,n+1){
            int tem = str[i-1] == 'T' ? 1 : 0;
            mat[i] = mat[i-1] + tem;
        }
        dp[0][0][0] = dp[0][0][1] = 0;
        FOR(i,0,m+1){
            if(str[0] == 'T'){
                dp[1][i][0] = i%2;
                dp[1][i][1] = 0 - dp[1][i][0];
            }
            else{
                dp[1][i][0] = (i+1)%2;
                dp[1][i][1] = 0 - dp[1][i][0];
            }
        }
        FOR(i,1,n+1){
            int d = mat[i-1]%2;
            if(str[i-1] == 'T'){
                    dp[i][0][0] = dp[i-1][0][0];
                    dp[i][0][1] = dp[i-1][0][1];
            }
            else{
                if(d){
                    dp[i][0][1] = dp[i-1][0][1] + 1;
                    dp[i][0][0] = dp[i-1][0][0] - 1;
                }
                else{
                    dp[i][0][0] = dp[i-1][0][0] + 1;
                    dp[i][0][1] = dp[i-1][0][1] - 1;
                }
            }
        }
        FOR(i,2,n+1){
            FOR(j,1,m+1){
                int d = dir(i-1,j);
                if(str[i-1] == 'T'){
                    dp[i][j][0] = dp[i-1][j][0];
                    dp[i][j][1] = dp[i-1][j][1];
                }
                else{
                    if(d){
                        dp[i][j][1] = dp[i-1][j][1] + 1;
                        dp[i][j][0] = dp[i-1][j][0] - 1;
                    }
                    else{
                        dp[i][j][0] = dp[i-1][j][0] + 1;
                        dp[i][j][1] = dp[i-1][j][1] - 1;
                    }
                }
                d = dir(i-1,j-1);
                if(str[i-1] == 'F'){
                    dp[i][j][0] = max(dp[i-1][j-1][0],dp[i][j][0]);
                    dp[i][j][1] = max(dp[i-1][j-1][1],dp[i][j][1]);
                }
                else{
                    if(d){
                        dp[i][j][1] = max(dp[i][j][1],dp[i-1][j-1][1]+1);
                        dp[i][j][0] = max(dp[i][j][0],dp[i-1][j-1][0]-1);
                    }
                    else{
                        dp[i][j][1] = max(dp[i][j][1],dp[i-1][j-1][1]-1);
                        dp[i][j][0] = max(dp[i][j][0],dp[i-1][j-1][0]+1);
                    }
                }
            }
        }
        printf("Case $%d:
",++tCase);
        printf("%d
",max(dp[n][m][0],dp[n][m][1]));
    }
    return 0;
}