http://codeforces.com/contest/752/problem/C
这题的意思其实就是叫你固定x个点，使得按顺序走这x个点后，产生的轨迹是给定的序列。
对于有若干条最短路径走到第i个点，这些情况可以忽略，就是你可以默认走的是任意一条最短路径。
对于一个序列，可以固定两个方向，只要一直都是这两个方向的，就不用设置点了。
比如一直都是RURURURURU,这些情况是不用设置点的，当另一个变量来的时候，比如需要D了，就需要设置一个点了。
有一些需要注意的地方是，
比如
RLL，这样只需要2个点。
RLR需要3个，
RLU需要两个。
就是本来是矛盾的两个东西，L和R矛盾，U和D矛盾。
就要考虑第三个东西，如果第三个和第一个一样的，就需要+2，其他的加1就好。
RLR第三个和第一个一样。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn = 1e6 + 20; char str[maxn]; vector<char>vc; bool vis[222][222]; void work() { int f; cin >> f; vis['L']['R'] = vis['R']['L'] = 1; vis['U']['D'] = vis['D']['U'] = 1; cin >> str + 1; int ans = 0; for (int i = 1; str[i]; ++i) { if (vc.size() == 2) { bool flag = 1; for (int j = 0; j < vc.size(); ++j) { if (str[i] == vc[j]) { flag = 0; break; } } if (!flag) continue; vc.clear(); vc.push_back(str[i]); ans++; } else { bool flag = 1; for (int j = 0; j < vc.size(); ++j) { if (vc[j] == str[i]) { flag = 0; break; } } if (!flag) continue; vc.push_back(str[i]); if (vc.size() == 2) { if (vis[vc[0]][vc[1]]) { if (i + 1 <= f && str[i + 1] != vc[0]) { ans++; vc.clear(); vc.push_back(str[i]); } else { vc.clear(); ans += 2; } } } } } if (vc.size()) ans++; cout << ans << endl; } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }