Educational Codeforces Round 103 (Rated for Div. 2) D Journey

隨便水篇題解：
定義一個 d p [ i ] [ 2 ] dp[i][2] dp[i][2]陣列

• d p [ i ] [ 0 ] dp[i][0] dp[i][0]代表從 i i i點向右最多能走多少個城市
• d p [ i ] [ 1 ] dp[i][1] dp[i][1]代表從 i i i點向左最多能走多少個城市

顯然我們向右走時如果是 RLRLRL 交替形式呢么能一直走下去，并且也可以原路回傳
我們向左走時如果是 LRLRLR 交替，也可以一直走下去，并且原路回傳

樣例：
LRRRLL
繪制成圖:

0 < ? ? 1 ? ? > 2 ? ? > 3 ? ? > 4 < ? ? 5 < ? ? 6 0<--1-->2-->3-->4<--5<--6 0<??1??>2??>3??>4<??5<??6

我們先求 d p [ i ] [ 0 ] dp[i][0] dp[i][0]陣列可以發現 我們不需要考慮 6 點，所以我們下標從1 開始，所以把 6 點映射為 7 點，所以此時 d p [ 7 ] [ 1 ] = 1 dp[7][1]=1 dp[7][1]=1

做出下表：

可得下面的轉移方程：

dp[n + 1][0] = 1;
    for (int i = n; i >= 1; i--) {
      if (s[i] == 'R' && s[i + 1] == 'L')
        dp[i][0] = dp[i + 2][0] + 2;
      else if (s[i] == 'R') {
        dp[i][0] = 2;
      } else {
        dp[i][0] = 1;
      }
    }

我們再求 d p [ i ] [ 1 ] dp[i][1] dp[i][1]陣列可以發現 我們不需要考慮 0 點，所以我們下標從0 開始了，所以把 1 點映射為 0 點，所以此時 d p [ 0 ] [ 1 ] = 1 dp[0][1]=1 dp[0][1]=1

做出下表：

可得下面的轉移方程：

 dp[0][1] = 1;
    for (int i = 1; i <= n; i++) {
      if (s[i] == 'L' && s[i - 1] == 'R') {
        dp[i][1] = dp[i - 2][1] + 2;
      } else if (s[i] == 'L') {
        dp[i][1] = 2;
      } else {
        dp[i][1] = 1;
      }
    }

然后對兩邊的答案進行相加去重即可

代碼

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node {
  ll a, b, c;
} p[100005];
int dp[300005][2];
char s[300005];
int main() {
  int t;
  cin >> t;
  for (int _ = 0; _ < t; _++) {
    int n;
    cin >> n;
    cin >> (s + 1);
    dp[n + 1][0] = 1;
    for (int i = n; i >= 1; i--) {
      if (s[i] == 'R' && s[i + 1] == 'L')
        dp[i][0] = dp[i + 2][0] + 2;
      else if (s[i] == 'R') {
        dp[i][0] = 2;
      } else {
        dp[i][0] = 1;
      }
    }
    dp[0][1] = 1;
    for (int i = 1; i <= n; i++) {
      if (s[i] == 'L' && s[i - 1] == 'R') {
        dp[i][1] = dp[i - 2][1] + 2;
      } else if (s[i] == 'L') {
        dp[i][1] = 2;
      } else {
        dp[i][1] = 1;
      }
    }
    for (int i = 0; i <= n; i++) {
      cout << dp[i][1] + dp[i + 1][0] - 1 << ' ';
    }
    puts("");
  }
  return 0;
}