HDU6739 Invoker 【dp】

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6739

借鉴了这个网址的题解：https://blog.csdn.net/qq_41785863/article/details/101676640

题意：每个大写字母代表一个技能，每个技能都由三个法球组成（无序的）。现在给出一串技能字符串，要求求出释放所有技能所需的最小按键次数、每输入一个法球按键一次，释放技能时需要按键一次（R）。

思路：因为技能的组成是无序的，也就是每个技能有6种组合方式，可以全部枚举出来。后一个技能也可以全部枚举出来，这样找到相邻技能36种组合中，链接起来时，法球数目最少的。即可以得到我们的状态转移方程。

dp[i][j]表示以j组合形式释放第i种技能时的最少按键次数。

代码如下：

 #include<stdio.h>

 #include<iostream>

 #include<string.h>

 #include<string>

 #include<map>

 #include<algorithm>

 #define mem(a, b) memset(a, b, sizeof(a))

 const int MAXN = 1e5 + ;

 const int inf = 0x3f3f3f3f;

 using namespace std;

 map<char, string> mp;

 char s[MAXN];

 int dp[MAXN][];

 int dir[][] = {, , ,

                  , , ,

                  , , ,

                  , , ,

                  , , ,

                  , , };

 int cal(string s, string s1, int x, int y)

 {

     int ret;

     if(s[dir[x][]] == s1[dir[y][]] && s[dir[x][]] == s1[dir[y][]] && s[dir[x][]] == s1[dir[y][]]) ret = ;

     else if(s[dir[x][]] == s1[dir[y][]] && s[dir[x][]] == s1[dir[y][]]) ret = ;

     else if(s[dir[x][]] == s1[dir[y][]]) ret = ;

     else ret = ;

     return ret;

 }

 int main()

 {

     mp['Y'] = "QQQ", mp['V'] = "QQW", mp['G'] = "QQE", mp['C'] = "WWW";

     mp['X'] = "QWW", mp['Z'] = "WWE", mp['T'] = "EEE", mp['F'] = "QEE";

     mp['D'] = "WEE", mp['B'] = "QWE";

     while(scanf("%s", s + ) != EOF)

     {

         int len = strlen(s + );

         mem(dp, inf);

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

             dp[][i] = ;

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

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

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

                     dp[i][j] = min(dp[i][j], dp[i - ][k] + cal(mp[s[i - ]], mp[s[i]], k, j) + );

         int ans = inf;

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

             ans = min(ans, dp[len][i]);

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

         }

     return ;

 }

巴特西

HDU6739 Invoker 【dp】

最新文章

热门文章