CF-Edu-103-D Journey （DP+前后缀）

题意： 现在有 n + 1 n + 1 n+1 个城市，每相邻的两个城市之间有一条路，并且每一条路都给定一个方向： L L L 或者 R R R ， L L L 表示 只能从 i − 1 i - 1 i−1 到 i i i ， R R R 表示只能从 i i i 到 i − 1 i - 1 i−1 。并且每过一秒，所有路径的方向都会变为相反的方向。现在问从任意一个城市出发，最多能走到多少城市。

思路： 乍一看，直接暴力，肯定 T L E TLE TLE ，想想能不能预处理，但是每次方向都会变，也不好预处理。然后稍微分析了一下，不难发现，从某一个城市出发，假设往左走，那左边的路必须是 L L L 的，若要继续往左，那么左边的左边的路原来必须是 R R R （因为每过一秒就会改变方向）。那么就能看出，要想走到最左边，必须是 L L L 开始的，并且 L L L 和 R R R 交替出现的，例如 L R L R L R L ⋯ LRLRLRL\cdots LRLRLRL⋯ ，反之，往右也是同理。那么只需要预处理出到第 i i i 个城市，上面这两种情况最长的结果，最后相加即可。

p r e [ i ] [ 0 ] pre[i][0] pre[i][0] ：表示到 i i i 为止，以 L L L 结尾的最长结果。

p r e [ i ] [ 1 ] pre[i][1] pre[i][1] ：表示到 i i i 为止，以 R R R 结尾的最长结果。

往右是同理。

代码：

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<cstring>
#include<string>
#include<algorithm>
#define fi first
#define se second
//#include<stdlib.h>
//#include <time.h>
//srand((unsigned)time(NULL));
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
using namespace std;
const int N = 2e6 + 10;

char s[N];
int main() {
//    ios_base::sync_with_stdio(0);
//    cin.tie(0);
//    cout.tie(0);
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        scanf("%s", s + 1);
        vector<vector<int>> pre(n + 1, vector<int>(2, 0));
        vector<vector<int>> suf(n + 1, vector<int>(2, 0));
        //0±íʾL£¬1±íʾR
        for (int i = 1; i <= n; i++) {
            if (s[i] == 'L') {
                pre[i][0] = pre[i - 1][1] + 1;
                pre[i][1] = 0;
            }
            else {
                pre[i][1] = pre[i - 1][0] + 1;
                pre[i][0] = 0;
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            if (s[i + 1] == 'R') {
                suf[i][1] = suf[i + 1][0] + 1;
                suf[i][0] = 0;
            }
            else {
                suf[i][0] = suf[i + 1][1] + 1;
                suf[i][1] = 0;
            }
        }
//        for (int i = 0; i <= n; i++) {
//            printf("%d ", pre[i][0]);
//        }
//        printf("\n");
//        for (int i = 0; i <= n; i++) {
//            printf("%d ", suf[i][1]);
//        }
//        printf("\n");
        for (int i = 0; i <= n; i++) {
            printf("%d ", pre[i][0] + suf[i][1] + 1);
        }
        printf("\n");
    }

    return 0;
}