Moo Route (USACO Silver 2023 January)
从0出发行走然后回到0，我们知道每一段 上面行走的次数，求回头走次数最少的走法。
这个是一个相对直观的构造方案的题，可以用递归的方式来思考，我们定义一个walk(l,r,h)函数，从l出发，走到r，然后再回到l，然后“消耗”掉h以上的所有行走次数。
那么下面是一个递归实现walk(l,r,h)的办法：
walk(l,r,h):
for (ll,rr) in split (l,r) by h+2 values:
walk(ll,rr,h+2) // back at ll
output R from ll to rr
output R on every intervening h+2 value
output L on r down to l
基本意思就是，从左往右走，在途中把h+2以上的高度使用递归的walk来全部走完，每次都回到起点，再接着往前走，走到r的时候，再回头一次性走回l。我们可以证明这样的一个走法，就是最优（转方向最少）的走法。
浴谷上的另外一个Greedy实现也是比较容易理解的。
以下是具体实现。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int a[100005];
// go from l to r then back to l
void walk(int l, int r, int h) {
int ll = l;
for (int rr = l; rr <= r+1; rr++) {
if (rr == r+1 || a[rr] == h+2) {
if (ll < rr)
walk(ll, rr-1, h+2); // walk all values above h+2 and back
for (int i=ll; i<rr; i++) // walk to rr
printf("R");
if (rr != r+1) // walk the h+2 at rr
printf("R");
ll = rr+1;
}
}
for (int i = r; i >= l; i--) {
printf("L");
}
}
int main() {
scanf("%d",&n);
for (int i = 0; i < n; i++) {
scanf("%d",&a[i]);
}
walk(0, n-1, 0);
return 0;
}