题解 CF1202C 【You Are Given a WASD-string...】
皎月半洒花
2019-08-15 20:56:39
这道题简直是`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~~