题目大意：n+1个点之间有n条单向路径，给定路径方向LR，L(i-1-->i)，R(i-->i-1)。从n+1个点开始，每次移动所有路径方向改变，问从n+1个点开始可到达的点的个数。
解题思路：手动模拟一下，会发现，当前点可向右经过的路径是RLRLRLRL...，向左可经过的路径是LRLRLRLR...。
那么，该点可向左移动点的个数+可向右移动点的个数+1是答案
例如 6 LRRRLL 可建立如下表
| 点 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 向右 | 0 | 1 | 1 | 2 | 0 | 0 | 0 |
| 向左 | 0 | 1 | 0 | 0 | 0 | 2 | 1 |
| 答案 | 1 | 3 | 2 | 3 | 1 | 3 | 2 |
那么问题在于如何得到可经过路径的长度，以向右为例
若i+1为0，也就是i+1为L。i为R，则ansr[i]=ansr[i+2]+2；i为L，则ansr[i]=0.
若i+1为1，也就是i+1为R。i为R，则ansr[i]=1；i为L，则ansr[i]=0
需要注意边缘问题
同理可得向左的路径长度。
1 #include<stdio.h> 2 #include<algorithm> 3 #include<string.h> 4 #include<math.h> 5 using namespace std; 6 7 typedef long long ll; 8 const int maxn=3e5+5; 9 int t,n,m; 10 char a[maxn]; 11 int dp[2][maxn]; 12 13 int main() 14 { 15 scanf("%d",&t); 16 while(t--) 17 { 18 scanf("%d",&n); 19 scanf("%s",a+1); 20 memset(dp,0,sizeof(dp)); 21 for(int i=n;i>=1;i--){ 22 if(a[i]=='R'){ 23 if(dp[0][i+1]==0&&i+2<=n+1){ 24 dp[0][i]=dp[0][i+2]+2; 25 } 26 else { 27 dp[0][i]=1; 28 } 29 }else { 30 dp[0][i]=0; 31 } 32 } 33 for(int i=1;i<=n;i++){ 34 if(a[i]=='L'){ 35 if(dp[1][i-1]==0&&i-2>=0){ 36 dp[1][i]=dp[1][i-2]+2; 37 } 38 else { 39 dp[1][i]=1; 40 } 41 }else { 42 dp[1][i]=0; 43 } 44 } 45 for(int i=0;i<=n;i++){ 46 printf("%d ",dp[0][i+1]+dp[1][i]+1); 47 } 48 printf(" "); 49 } 50 return 0; 51 } 52 /* 53 2 54 3 55 LRL 56 3 57 RLR 58 */