C. Santa Claus and Robot 思考题

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 + ;

char str[maxn];

vector<char>vc;

bool vis[][];

void work() {

    int f;

    cin >> f;

    vis['L']['R'] = vis['R']['L'] = ;

    vis['U']['D'] = vis['D']['U'] = ;

    cin >> str + ;

    int ans = ;

    for (int i = ; str[i]; ++i) {

        if (vc.size() == ) {

            bool flag = ;

            for (int j = ; j < vc.size(); ++j) {

                if (str[i] == vc[j]) {

                    flag = ;

                    break;

                }

            }

            if (!flag) continue;

            vc.clear();

            vc.push_back(str[i]);

            ans++;

        } else {

            bool flag = ;

            for (int j = ; j < vc.size(); ++j) {

                if (vc[j] == str[i]) {

                    flag = ;

                    break;

                }

            }

            if (!flag) continue;

            vc.push_back(str[i]);

            if (vc.size() == ) {

                if (vis[vc[]][vc[]]) {

                    if (i +  <= f && str[i + ] != vc[]) {

                        ans++;

                        vc.clear();

                        vc.push_back(str[i]);

                    } else {

                        vc.clear();

                        ans += ;

                    }

                }

            }

        }

    }

    if (vc.size()) ans++;

    cout << ans << endl;

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    work();

    return ;

}