首页 > ACM题库 > HDU-杭电 > hdu 2677 Dota all stars-递归和分治-[解题报告]C++
2014
02-12

hdu 2677 Dota all stars-递归和分治-[解题报告]C++

Dota all stars

问题描述 :

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.

     

               

     

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.

输入:

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 )

输出:

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 )

样例输入:

4
欢欣之刃 100
敏捷之靴 20
半兽人之斧 100
力量腰带 50
2
散华 1
力量腰带 2
3
欢欣之刃 + 敏捷之靴 = 散华
半兽人之斧 + 力量腰带 = 夜叉
散华 + 夜叉 = 散夜对剑
1
散夜对剑 2

5
鹰角弓 3200
短棍 1100
攻击之爪 950
阔剑 1200
恶魔刀锋 2600
0
3
鹰角弓 + 短棍 = 蝴蝶
攻击之爪 + 阔剑 = 水晶剑
水晶剑 + 恶魔刀锋 = 大炮
2
蝴蝶 1
大炮 1

样例输出:

320
9050

    题目本身不难。存储一下每个武器的合成方式,递归求和即可。关键在于它简单,而且写代码又挺复杂。。。一直想在网上找代码A过去的,因为这是我ACM Step 4.3最后一题,可是一直找不到,还是得自己打代码。不过现在大家可以直接Copy我的代码A过去了

#include <iostream>
#include <string>
using namespace std;

int n,sum;

class dynamicArray
{
private:
    int num;
public:
    dynamicArray *next;
    //    构造函数
    dynamicArray():num(0),next(0)
    {
    }
    dynamicArray(int n):num(n),next(0)
    {
    }
    //    添加数字
    void addNum(int n)
    {
        dynamicArray *p=this;
        while(p->next)
            p=p->next;
        p->next=new dynamicArray(n);
    }
    //    获取数字
    int getNum()
    {
        return num;
    }
    //    获取Next地址
    dynamicArray* getNext()
    {
        return next;
    }
    //    清空
    void clean()
    {
        dynamicArray *p=this;
        if(p->next)
        {
            p->next->clean();
            delete p->next;
            p->next=0;
        }
    }
};

struct sword
{
    string name;
    int value;
    int num;
    dynamicArray a;
} s[100];

int find(string &str)
{
    int i;
    for(i=0;i<n;i++)
        if(s[i].name==str)
            return i;
    return -1;
}

void getValue(int t,int num)
{
    dynamicArray *p;
    if(s[t].num>=num)
        s[t].num-=num;
    else
    {
        num-=s[t].num;
        s[t].num=0;
        if(s[t].value==0)
        {
            p=s[t].a.next;
            while(p)
            {
                getValue(p->getNum(),num);
                p=p->next;
            }
        }
        else
            sum+=s[t].value*num;
    }
}

int main()
{
    char ch;
    string str;
    int m,i,j,t,num;
    dynamicArray a,*p;
    while(cin>>n)
    {
        sum=0;
        memset(s,0,sizeof(s));
        for(i=0;i<n;i++)
        {
            cin>>s[i].name;
            cin>>s[i].value;
        }
        cin>>m;
        for(i=0;i<m;i++)
        {
            cin>>str>>num;
            if((t=find(str))==-1)
            {
                s[n].name=str;
                s[n++].num=num;
            }
            else
            {
                s[t].num=num;
            }
        }
        cin>>m;
        for(i=0;i<m;i++)
        {
            a.clean();
            while(cin>>str>>ch)
            {
                a.addNum(find(str));
                if(ch=='=')
                {
                    cin>>str;
                    if((t=find(str))==-1)
                    {
                        s[n].name=str;
                        t=n++;
                    }
                    s[t].a.next=a.getNext();
                    a.next=0;
                    break;
                }
            }
        }
        cin>>m;
        for(i=0;i<m;i++)
        {
            cin>>str>>num;
            t=find(str);
            getValue(t,num);
        }
        cout<<sum<<endl;
    }
}

 

解题转自:http://www.cnblogs.com/IT-BOY/archive/2013/03/08/2949103.html


  1. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  2. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!