D. Journey(dp)

题意

​ 给定数轴上$n+1$个点，$n$条有向边，对$i\in [0,n]$，从$i$点出发能遍历的最大点个数，每次经过一条边后，所有边反向。

---

思路

​ 依题可知，从$i$开始的路径肯定不能往回走，因为只有两个方向，我们只需考虑点$i$往左走的贡献和往右的贡献。递推就很简单了，如果$s[i]!=s[i-1],l[i]=l[i-1]+1$。只要边方向不同，贡献加1。

向右递推类似。

时间复杂度：$O(n)$

---

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int t,n,l[N],r[N]; 
char s[N];
int main(){	
	int t;scanf("%d",&t);
	while(t--){
		scanf("%d%s",&n,s+1);
		l[1]=1;
		for(int i=2;i<=n;i++){
			if(s[i]!=s[i-1]) l[i]=l[i-1]+1;
			else l[i]=1;
		}
		r[n]=1;
		for(int i=n-1;i;i--) 
			if(s[i]!=s[i+1]) r[i]=r[i+1]+1;
			else r[i]=1;
		for(int i=0;i<=n;i++){
			int x=(!i||s[i]!='L')?0:l[i];
			int y=(i==n||s[i+1]!='R')?0:r[i+1];
			printf("%d ",x+y+1); 
		}printf("\n");
	}
	return 0;
}