有一个长度为n的楼梯，每节台阶上有一个字符串
求从第i个台阶开始要走出这N个台阶需要的步数(即从1号台阶向下，或N号台阶向上）
若出不去则输出-1
首先考虑第i个位置是U，显然它会走到第一个D反向，之后到i下面的第一个U再次反向，显然这部分后面就不会再影响答案了
于是可以很容易的得出第i个位置是从上还是从下走出去的
然后就只需要计算折返的距离即可
#include<bits/stdc++.h> using namespace std; #define LL long long inline LL read() { LL f = 1 , x = 0; char ch; do { ch = getchar(); if(ch==‘-‘) f=-1; } while(ch<‘0‘||ch>‘9‘); do { x=(x<<3) + (x<<1) + ch - ‘0‘; ch = getchar(); }while(ch>=‘0‘&&ch<=‘9‘); return f*x; } const int MAXN = 1000000 + 10; int n; char s[MAXN]; long long ans[MAXN]; int l[MAXN],r[MAXN]; queue<int>q; int main() { n = read(); scanf("%s",s+1); for(int i=1;i<=n;i++) l[i] = l[i-1] + (s[i] == ‘U‘); for(int i=n;i>=1;i--) r[i] = r[i+1] + (s[i] == ‘D‘); for(int i=1;i<=n;i++) if(l[i] <= r[i+1]) ans[i] = i;else ans[i] = n - i + 1; LL res = 0; for(int i=1;i<=n;i++) { res += q.size(); while(q.size() > r[i]) {res -= i - q.front();q.pop();} ans[i] += res * 2; if(s[i] == ‘U‘) q.push(i); } while(q.size()) q.pop(); res = 0; for(int i=n;i>=1;i--) { res += q.size(); while(q.size() > l[i]) {res -= q.front() - i;q.pop();} ans[i] += res * 2; if(s[i] == ‘D‘) q.push(i); } for(int i=1;i<=n;i++) printf("%lld ",ans[i]); }
原文：https://www.cnblogs.com/wlzs1432/p/13971521.html