链接:

http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1009&cid=872

题意:

在 dota2 中有一个叫做祈求者(Invoker)的英雄，在游戏中他有三个基础技能：冰(Quas)，雷(Wex)，火(Exort)，每施展一个技能就可以获得相应属性的一个法球(element)。

但是祈求者同时最多只能有三个法球，即如果他在有三个法球的状态下又使用了某个法球技能，那么他会获得该法球，并失去之前三个法球中最先获得的一个。

不难得出，祈求者身上的三个法球的无顺序组合有 10 种，每一种都对应着一个组合技能：

急速冷却(Cold Snap)，无序组合 QQQ，用 Y 表示
幽灵漫步(Ghost Walk)，无序组合 QQW，用 V 表示
寒冰之墙(Ice Wall)，无序组合 QQE，用 G 表示
电磁脉冲(EMP)，无序组合 WWW，用 C 表示
强袭飓风(Tornado)，无序组合 QWW，用 X 表示
灵动迅捷(Alacrity)，无序组合 WWE，用 Z 表示
阳炎冲击(Sun Strike)，无序组合 EEE，用 T 表示
熔炉精灵(Forge Spirit)，无序组合 QEE，用 F 表示
混沌陨石(Chaos Meteor)，无序组合 WEE，用 D 表示
超震声波(Deafening Blast)，无序组合 QWE，用 B 表示

当祈求者拥有三个法球的时候，使用元素祈唤(Invoke)技能，用 R 表示，便可获得当前法球组合所对应的技能，同时原有的三个法球也不会消失，先后顺序的状态也不会改变。

现在给定一个技能序列，你想按照给定的顺序将他们一个一个地祈唤出来，同时你想用最少的按键来达到目标，所以你想知道对于给定的一个技能序列，最少按多少次键才能把他们都祈唤出来。

注意：游戏开始的时候，祈求者是没有任何法球的。

思路:

先打表每种情况, DP搞一下

每个点有6重情况, 暴力处理, 多组数据.....

代码:

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MAXN = 1e5+10;

char Opt[15][6][5] = {{"QQQ", "QQQ", "QQQ", "QQQ", "QQQ", "QQQ"},

                      {"QQW", "QWQ", "QQW", "QWQ", "WQQ", "WQQ"},

                      {"QQE", "QEQ", "QQE", "QEQ", "EQQ", "EQQ"},

                      {"WWW", "WWW", "WWW", "WWW", "WWW", "WWW"},

                      {"QWW", "QWW", "WQW", "WWQ", "WQW", "WWQ"},

                      {"WWE", "WEW", "WWE", "WEW", "EWW", "EWW"},

                      {"EEE", "EEE", "EEE", "EEE", "EEE", "EEE"},

                      {"QEE", "QEE", "EQE", "EEQ", "EQE", "EEQ"},

                      {"WEE", "WEE", "EWE", "EEW", "EWE", "EEW"},

                      {"QWE", "QEW", "WQE", "WEQ", "EQW", "EWQ"}};

map<char, int> Mp;

char s[MAXN];

int Dp[MAXN][6];

bool Check(char *l, char *r)

{

    int len = strlen(l);

    for (int i = 0;i < len;i++)

    {

        if (l[i] != r[i])

            return false;

    }

    return true;

}

int Count(char *l, char *r)

{

    if (Check(l, r))

        return 0;

    if (Check(l+1, r))

        return 1;

    if (Check(l+2, r))

        return 2;

    return 3;

}

void Init()

{

    Mp['Y'] = 0;

    Mp['V'] = 1;

    Mp['G'] = 2;

    Mp['C'] = 3;

    Mp['X'] = 4;

    Mp['Z'] = 5;

    Mp['T'] = 6;

    Mp['F'] = 7;

    Mp['D'] = 8;

    Mp['B'] = 9;

}

int main()

{

    Init();

    scanf("%s", s);

    int len = strlen(s);

    memset(Dp, 0x3f3f3f, sizeof(Dp));

    for (int i = 0; i < 6; i++)

        Dp[0][i] = 3;

    for (int i = 1; i < len; i++)

    {

        for (int j = 0; j < 6; j++)

        {

            for (int k = 0; k < 6; k++)

            {

                int cnt = Count(Opt[Mp[s[i - 1]]][k], Opt[Mp[s[i]]][j]);

//                cout << Opt[Mp[s[i-1]]][k] << ' ' << Opt[Mp[s[i]]][j] << ' ' << cnt << endl;

                Dp[i][j] = min(Dp[i][j], Dp[i - 1][k] + cnt);

            }

        }

    }

    int ans = Dp[len - 1][0];

    for (int i = 0; i < 6; i++)

        ans = min(ans, Dp[len - 1][i]);

//        for (int i = 0; i < len; i++)

//        {

//            for (int j = 0; j < 6; j++)

//                cout << Dp[i][j] << ' ';

//            cout << endl;

//        }

    printf("%d\n", ans + len);

    return 0;

}

巴特西

2019CCPC秦皇岛赛区（重现赛）- I

链接:

题意:

思路:

代码:

最新文章

热门文章