题解 CF1202C 【You Are Given a WASD-string...】

皎月半洒花

2019-08-15 20:56:39

Solution

这道题简直是`debug`到吐血…… 其实思路是很**明晰+清新**的,大概就是你考虑首先显然是**行列无关**的,所以分开考虑;接着你发现我们的最优策略肯定是让某一步相当于每走,但是假设我的$x_{min}$和$x_{max}$均在我这次改动操作的后面,那么我们尝试缩小活动范围,即缩小$x_{max}$的时候也会缩小$x_{min}$,相当于没缩——所以我们应找到一个界点,所有的最大值都在左/右边,对应的所有最小值都在右/左边。 于是我们考虑直接前缀和瞎搞就可以了。但是我`debug`了很久的原因是,这个问题他不是很完美,详细一些就是我们考虑无论怎么移动,都不能越过我们预处理出来的$x_{min}$、$x_{max}$这个界(否则会出现越贪越大)。也就是说,假设一开始我有一个$x_{max}$,接着过了一会儿有一个$x_{min}$,为了“拔高”$x_{min}$我们必须要添加一个$W$,所以我们必须要保证任何时刻不会出现$x_{max}$在放上一个$W$之后越界的情况,也就是说$x_{min}$和$x_{max}$出现的位置之间必须要一个$S$才能用来抵消掉我们$W$。 以上全都是以`W/S`作为例子的,`A/D`的情况分类讨论一下就好。 呃,废话有点多,但是实际上写起来~~挺好写的吧~~也需要一些时间: ```cpp #define MAXN 200010 #define LL long long #define Inf 192608170 using namespace std ; LL ans ; int fhm, fhn, fwm, fwn, pos[2][5], i ; int T, N, Sw[MAXN], Sh[MAXN] ; char S[MAXN] ; int main(){ cin >> T ; while (T --){ fhm = fwm = -Inf, fhn = fwn = Inf ; scanf("%s", S + 1), N = strlen(S + 1) ; for (i = 1 ; i <= N ; ++ i){ Sh[i] = Sh[i - 1], Sw[i] = Sw[i - 1] ; if (S[i] == 'W') Sh[i] = Sh[i - 1] + 1 ; else if (S[i] == 'S') Sh[i] = Sh[i - 1] - 1 ; else if (S[i] == 'D') Sw[i] = Sw[i - 1] + 1 ; else if (S[i] == 'A') Sw[i] = Sw[i - 1] - 1 ; }//前缀和 : w x h for (i = 0 ; i <= N ; ++ i) fwm = max(Sw[i], fwm), fwn = min(Sw[i], fwn) ; for (i = 0 ; i <= N ; ++ i) fhm = max(Sh[i], fhm), fhn = min(Sh[i], fhn) ; for (i = N ; ~i ; -- i) if (Sh[i] == fhn) { pos[0][4] = i ; break ; } //last_min h for (i = N ; ~i ; -- i) if (Sw[i] == fwn) { pos[1][4] = i ; break ; } //last_min h for (i = 0 ; i <= N ; ++ i) if (Sh[i] == fhm) { pos[0][1] = i ; break ; } //first_max h for (i = 0 ; i <= N ; ++ i) if (Sw[i] == fwm) { pos[1][1] = i ; break ; } //first_max w for (i = N ; ~i ; -- i) if (Sh[i] == fhm) { pos[0][3] = i ; break ; } //last_max h for (i = N ; ~i ; -- i) if (Sw[i] == fwm) { pos[1][3] = i ; break ; } //last_max h for (i = 0 ; i <= N ; ++ i) if (Sh[i] == fhn) { pos[0][2] = i ; break ; } //first_min h for (i = 0 ; i <= N ; ++ i) if (Sw[i] == fwn) { pos[1][2] = i ; break ; } //first_min w ans = 1ll * (fwn - fwm - 1) * (fhn - fhm - 1) ; //cout << ans << endl ; if (pos[0][3] < pos[0][2] && Sh[pos[0][3]] - Sh[pos[0][2]] > 1) ans = min(ans, 1ll * (fhm - fhn) * (fwm - fwn + 1)) ; if (pos[1][3] < pos[1][2] && Sw[pos[1][3]] - Sw[pos[1][2]] > 1) ans = min(ans, 1ll * (fhm - fhn + 1) * (fwm - fwn)) ; if (pos[0][4] < pos[0][1] && Sh[pos[0][4]] - Sh[pos[0][1]] < -1) ans = min(ans, 1ll * (fhm - fhn) * (fwm - fwn + 1)) ; if (pos[1][4] < pos[1][1] && Sw[pos[1][4]] - Sw[pos[1][1]] < -1) ans = min(ans, 1ll * (fhm - fhn + 1) * (fwm - fwn)) ; cout << ans << endl ; pos[0][1] = pos[1][1] = pos[0][2] = pos[1][2] = Inf ; pos[0][3] = pos[1][3] = pos[0][4] = pos[1][4] = -Inf ; } } ``` ~~嘤嘤嘤鬼知道我做这题时经历了什么啊qaq~~