1476D. Journey

D. Journey

一道简单线性dp #include <bits/stdc++.h> using namespace std; const int N = 5e5 + 3; char str[N]; int a[N],b[N]; int main() {int t;cin>>t;while (t--){int n;cin>>n;cin>>str+1;for (int i=0;i<=n;i++) a[i] = b[i] = 1;if (str[1]=='L') a[1] = 2;for (int i=2;i<=n;i++){if (str[i]=='L'&&str[i-1]=='R') a[i] = a[i-2]+2;else if (str[i]=='L') a[i] = 2;}if (str[n]=='R') b[n-1] = 2;for (int i=n-2;i>=0;i--){if (str[i+1]=='R'&&str[i+2]=='L') b[i] = b[i+2]+2;else if (str[i+1]=='R') b[i] = 2;}for (int i=0;i<=n;i++) cout<<a[i]+b[i]-1<<" ";cout<<endl;} }

总结

以上是生活随笔为你收集整理的1476D. Journey的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。