D. Journey

一道簡(jiǎn)單線性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;} }

總結(jié)

以上是生活随笔為你收集整理的1476D. Journey的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。