题解 AT3726 [ARC087B] FT Robot

首先可以观察到一个非常重要的性质：对于一次前进的操作，如果前面有奇数次转向，则走上下，否则走左右。（当然如果一开始就前进就只能走右）

于是我们可以将其拆成许多的“块”，并分成两类，即前进方向为左右还是上下。

然后对于两个维度分别 dp 。

\(f_{i},_{j}=f_{i-1},_{j-val} \ | \ f_{i-1},_{j+val}\)

\(g\) 同理。

当然还要对负数的情况以及边界进行一下处理。

code:

#include <bits/stdc++.h>
using namespace std;
const int N = 8000 + 5, nn = 8000;
string s;
int len, ex, ey, tot = 0;
bool f[2][N * 2], g[2][N * 2];
struct node{int type, num;}a[N];
vector<int> v[2];
int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> s >> ex >> ey; len = s.size(); s = "." + s;
	int cnt = 0, flag = 0;
	for (int i = 1; i <= len; ++i) { //预处理出每个块 
		if (s[i] == 'F') {
			if (!flag) a[++tot].type = cnt % 2, a[tot].num = 1, flag = 1;
			else if (flag) ++a[tot].num;
		} else {
			flag = 0;
			++cnt;
		}
	}
	int st = 1, t = 0, t2 = 0;
	if (s[1] == 'F') st = 2, f[0][a[1].num + nn] = 1; //单独处理一下一开始就前进的情况 
	for (int i = st; i <= tot; ++i) v[a[i].type].push_back(a[i].num);
	g[0][nn] = 1;
	if (st == 1) f[0][nn] = 1;
	for (int i = 0; i < v[0].size(); ++i) { //横坐标DP 
		for (int j = -nn; j <= nn; ++j) {
			f[t ^ 1][j + nn] = 0;
			if (j - v[0][i] >= -nn) f[t ^ 1][j + nn] |= f[t][j - v[0][i] + nn];
			if (j + v[0][i] <= nn) f[t ^ 1][j + nn] |= f[t][j + v[0][i] + nn];
		}
		t ^= 1;
	}
	for (int i = 0; i < v[1].size(); ++i) { //纵坐标DP 
		for (int j = -nn; j <= nn; ++j) {
			g[t2 ^ 1][j + nn] = 0;
			if (j - v[1][i] >= -nn) g[t2 ^ 1][j + nn] |= g[t2][j - v[1][i] + nn];
			if (j + v[1][i] <= nn) g[t2 ^ 1][j + nn] |= g[t2][j + v[1][i] + nn];
		}
		t2 ^= 1;
	}
	if (f[t][ex + nn] && g[t2][ey + nn]) cout << "Yes" << endl; //如果都能达到，输出Yes 
	else cout << "No" << endl;
	return 0;
}