HDU 2677 Dota all stars 【dfs练习】

深藏阁楼爱情的钟 2022-06-05 12:54 113阅读 0赞

## Dota all stars ##

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 1141 Accepted Submission(s): 333

#### Problem Description ####

> Dota as a popular computer game has serval years. Lots of Dota fans know that the equipment in the game is very important. To get a excellent equipment may be pass many processes. Look the picture, you may see that in order to get the finally one must get the other two first. But this two may be can not get directly.
> 
> ![这里写图片描述][SouthEast]  
> Now give the primary equipments which you can buy it by money directly in the shop.  
> And the numbers of equipments you already have.  
> You also know all the formulas how to get a new better equipment by primary equipments.  
> Last give the numbers of equipments you want, tell us how much extra money you need.

#### Input ####

> The input contains multiple test cases.  
> First part a integer n1 expressing the numbers of primary equipments you can buy in the shop.  
> Next n1 lines, each line form as S V,S is the name of equipment and V meaning you should cost V money to buy one equipments S.  
> Second part a integer n2 expressing the numbers of kinds equipments you have.  
> Next n2 lines, each line form as S,M, meaning the numbers of equipment S you have is M.  
> Third part a integer n3 expressing the numbers of formulas.  
> Next n3 lines, each line have a character ‘=’, The left is the equipments you should use to get the right equipment. For example A + B + C = D, In order to get a D, you must use A,B,C,D.each one.  
> Last part a integer n4, expressing n4 kinds of equipments you need.  
> Than n4 lines, each line form as S,M. Meaning the numbers of equipment S you need is M.
> 
> You may sure the total kinds of equipment will not larger than 100. And the lengths of equipment name will less than 50.(a chinese words made up of two character )

#### Output ####

> Output the extra money you need to achieve goal.

#### Sample Input ####

> 4  
> 欢欣之刃 100  
> 敏捷之靴 20  
> 半兽人之斧 100  
> 力量腰带 50  
> 2  
> 散华 1  
> 力量腰带 2  
> 3  
> 欢欣之刃 + 敏捷之靴 = 散华  
> 半兽人之斧 + 力量腰带 = 夜叉  
> 散华 + 夜叉 = 散夜对剑  
> 1  
> 散夜对剑 2
> 
> 5  
> 鹰角弓 3200  
> 短棍 1100  
> 攻击之爪 950  
> 阔剑 1200  
> 恶魔刀锋 2600  
> 0  
> 3  
> 鹰角弓 + 短棍 = 蝴蝶  
> 攻击之爪 + 阔剑 = 水晶剑  
> 水晶剑 + 恶魔刀锋 = 大炮  
> 2  
> 蝴蝶 1  
> 大炮 1

#### Sample Output ####

> 320  
> 9050

#### 题意概括： ####

商店里有n1种武器每个武器都给出价格，现在你有n2种武器每种都有m个，再给你n3种武器的合成方式（每个武器可能不止由两种合成）。现在让你合成n4种武器，每种武器都要合成一定的数量。

#### 解题分析： ####

这道题就是一道简单的分治+递归，dfs对每种武器搜索一遍看是由哪几种武器合成的，并去掉已有武器的价格就可以了。就是数据处理有点麻烦，用map对每一种武器都进行编号就可以了。

#### AC代码： ####

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<string>
    #include<map>
    
    using namespace std;
    
    #define N 105
    
    struct node{
        int v, len, flag, sy[N];
    }u[N];
    
    int dfs(int x)
    {
        int i, j, k, sum = 0;
        if(u[x].len) {u[x].len--; return 0;}
        if(u[x].flag){
            for(i = 0; i < u[x].flag; i++){
                k = u[x].sy[i];
                sum += dfs(k);
            }
            return sum+u[x].v;
        }
        return u[x].v;
    }
    
    int main()
    {
        char s[N], a[N][N];
        int b[N];
        int n, i, j, k, c, t, sum, h;
        map<string, int> mp;
        while(~scanf("%d", &n)){
            memset(u, 0, sizeof(struct node)*N);
            mp.clear();
            k = 1;
            while(n--){
                scanf("%s%d", s, &c);
                if(!mp[s]) mp[s] = k++;
                u[mp[s]].v = c;
            }
            scanf("%d", &n);
            while(n--){
                scanf("%s%d", s, &c);
                if(!mp[s]) mp[s] = k++;
                u[mp[s]].len = c;
            }
            scanf("%d", &n);
            for(j = 0; j < n; j++){
                for(i = 0; ; i++){
                    scanf("%s", s);
                    if(s[0] == '+'){i--; continue;}
                    else if(s[0] == '=') break;
                    if(!mp[s]) mp[s] = k++;
                    b[i] = mp[s];
                }
                scanf("%s", a[j]);
                if(!mp[a[j]]) mp[a[j]] = k++;
                u[mp[a[j]]].flag = i;
                memcpy(u[mp[a[j]]].sy, b, sizeof(int)*i);
            }
            scanf("%d", &n);
            sum = 0;
            while(n--){
                scanf("%s%d", s, &c);
                t = mp[s];
                while(c--) sum += dfs(mp[s]);
            }
            printf("%d\n", sum);
        }
        return 0;
    }

[SouthEast]: /images/20220605/d1b87a6a7b9e421d81ffde775443b521.png