首页 > 搜索 > DFS搜索 > HDU 4269-Defend Jian Ge-模拟-[解题报告]HOJ
2015
05-23

HDU 4269-Defend Jian Ge-模拟-[解题报告]HOJ

Defend Jian Ge

问题描述 :

Defend Jian Ge, an interesting RPG map in WAR3, has a very complete equipment system as a mini RPG game.
In the game, each player has a backpack which has 6 grids and some gold reserves. There are three kinds of equipments in the game.
1. Normal equipment: Each equipment occupies one grid in the backpack and the player can buy it directly. The value of the normal equipment is equal to its price.
2. Mixture equipment: Each equipment occupies one grid in the backpack and the player can only get it through the synthesis of the corresponding recipe. If you have enough equipment of recipes in your backpack and gold to pay synthesis cost, you can get it. The value of the mixture equipment is equal to the sum of all equipments’ value in the recipe plus the synthesis cost. A mixture equipment can be made from several normal equipments and mixture equipments.
3. Consume equipment: A kind of equipment must occupy one grid and the player can buy it directly. That is to say, if you have a number of consume equipments, they must be in one grid. The value of each consume equipment is equal to its price, and when you want to sell this kind of equipment, you must sell the whole grid’s equipments at the same time.

Alice and Bob

You should pay attention:
1. When the backpack is full, you cannot buy anything.
2. When a mixture equipment is get, the mixture equipment of recipe in you backpack will disappear.
3. If one operation is illegal, there is nothing happened in your backpack and gold.
4. Initially, there is nothing in your backpack and you have 0 gold.
5. The gold you have cannot be a negative number.

As a DS programmer, you want to simulate the dynamic states in your backpack by program. Now you have initial state and several operations, you wonder the final state.

输入:

There are multiple test cases.
The first line contains an integer N1 (0 <= N1 <= 20) indicating the kind of normal equipment.
The next N1 lines each line contains a string and an integer indicating the name of this normal equipment and its price respectively.
**Format: str num
The following line contains an integer N2 (0 <= N2 <= 20) indicating the kind of mixture equipment.
Each of the next N2 lines begins with a string and an integer indicating the name of this mixture equipment and its synthesis cost. Following, the synthesis recipe of this kind of equipment: some pairs of string and integer indicating which kind of equipment and the number you need to synthesis.
**Format: str num: str1 num1, str2 num2, … , strn numn (num1 + num2 + … +numn<=6 and numi >= 0 (1 <= i <= n))
The next line contains an integer N3 (0 <= N3 <= 20) indicating the kind of consume equipment.
Each of the next N3 lines contains a string and an integer indicating the name of this consume equipment and it’s price.
**Format: str num
The next line contains an integer M (0 <= M <= 100) indicating the number of operation.
Each of the next M lines contains an operation.
There are three kinds of operation:
1. +num indicating you get num gold (0 <= num <= 1000).
2. +str indicating you want to get an equipment whose name is str.
3. -str indicating you want to sell the equipment whose name is str. If you sell the equipment, you can get gold that is the same to its value.

There is a blank line after each case.
All strings of name only contain lowercase character and its length is no more than 15. The price of the equipment is a non-negative integer which is no more than 1000.

输出:

There are multiple test cases.
The first line contains an integer N1 (0 <= N1 <= 20) indicating the kind of normal equipment.
The next N1 lines each line contains a string and an integer indicating the name of this normal equipment and its price respectively.
**Format: str num
The following line contains an integer N2 (0 <= N2 <= 20) indicating the kind of mixture equipment.
Each of the next N2 lines begins with a string and an integer indicating the name of this mixture equipment and its synthesis cost. Following, the synthesis recipe of this kind of equipment: some pairs of string and integer indicating which kind of equipment and the number you need to synthesis.
**Format: str num: str1 num1, str2 num2, … , strn numn (num1 + num2 + … +numn<=6 and numi >= 0 (1 <= i <= n))
The next line contains an integer N3 (0 <= N3 <= 20) indicating the kind of consume equipment.
Each of the next N3 lines contains a string and an integer indicating the name of this consume equipment and it’s price.
**Format: str num
The next line contains an integer M (0 <= M <= 100) indicating the number of operation.
Each of the next M lines contains an operation.
There are three kinds of operation:
1. +num indicating you get num gold (0 <= num <= 1000).
2. +str indicating you want to get an equipment whose name is str.
3. -str indicating you want to sell the equipment whose name is str. If you sell the equipment, you can get gold that is the same to its value.

There is a blank line after each case.
All strings of name only contain lowercase character and its length is no more than 15. The price of the equipment is a non-negative integer which is no more than 1000.

样例输入:

[pre]2
ring 1
sword 2
1
knife 3: ring 1, sword 1
1
medicine 1
4
+100
+ring
+sword
+knife

1
shoe 0
1
wing 1: 
1
medicine 1
3
+10
+shoe
+wing

1
shoe 0
1
wing 1: 
1
medicine 1
4
+10
+shoe
+wing
-wing

1
shoe 1
1
wing 1: shoe 1
1
medicine 1
8
+100
+shoe
+shoe
+shoe
+shoe
+shoe
+medicine
+medicine

[/pre]

样例输出:

[pre]Case 1:
94
1
knife: 1

Case 2:
9
2
shoe: 1
wing: 1

Case 3:
10
1
shoe: 1

Case 4:
94
6
medicine: 1
shoe: 1
shoe: 1
shoe: 1
shoe: 1
shoe: 1

[/pre]

题意:模拟RPG,表示没玩过魔兽的很伤~~
题解:需要注意的是,
格子只有6个,如果格子满了能得到东西,即使有足够的钱,即使格子里有consume物品也不能买相同的consume物品,但是可以合成需要物品总数
         不为0的物品。开始想把所有合成的物品的价格处理出来,但是由于给定的顺序不定,合成物品的物品还可能是合成的,这样需要给物品标定等级,dfs太麻烦,想想
         由于是模拟,合成物品是按照给定的指令来的,在格子中的物品是有价格的,所以没必要处理合成物品的价格了。

Sure原创,转载请注明出处。

#include <iostream>
#include <cstdio>
#include <memory.h>
#include <string.h>
#include <algorithm>
#define MAX(a , b) ((a) > (b) ? (a) : (b))
using namespace std;
const int maxn = 22;
const int maxm = 8;
struct node
{
    char name[maxn];
    int price;
}th[maxn],consume[maxn];
struct thing
{
    char name[maxn];
    int need,cnt;
    char dic[maxm][maxn];
    int num[maxm];
}com[maxn];
struct SS
{
    char name[maxn];
    int num,price;
    bool valid;
    bool operator < (const SS &other) const
    {
        return strcmp(name , other.name) <= 0;
    }
}bag[maxm];
char str[1000];
int m,n1,n2,n3,top,cas = 0;

int change(char *s)
{
    int res = 0;
    for(int i=0;s[i] != '\0';i++)
    {
        res *= 10;
        res += s[i] - '0';
    }
    return res;
}

void read()
{
    printf("Case %d:\n",++cas);
    for(int i=0;i<n1;i++)
    {
        getchar();
        scanf("%s %d",th[i].name,&th[i].price);
    }
    scanf("%d",&n2);
    getchar();
    for(int i=0;i<n2;i++)
    {
        gets(str);
        char *g = NULL;
        g = strtok(str , ",: \t");
        strcpy(com[i].name , g);
        g = strtok(NULL , ",: \t");
        com[i].need = change(g);
        com[i].cnt = 0;
        g = strtok(NULL , ",: \t");
        while(g != NULL)
        {
            strcpy(com[i].dic[com[i].cnt] , g);
            g = strtok(NULL , ",: \t");
            com[i].num[com[i].cnt++] = change(g);
            g = strtok(NULL , ",: \t");
        }
    }
    scanf("%d",&n3);
    for(int i=0;i<n3;i++)
    {
        getchar();
        scanf("%s %d",consume[i].name,&consume[i].price);
    }
    return;
}

void update()
{
    int j = 0;
    for(int i=0;i<6;i++)
    {
        while(j < 6 && bag[j].valid)
        {
            j++;
        }
        if(bag[i].valid == false) continue;
        if(i > j)
        {
            bag[j] = bag[i];
            bag[i].valid = false;
            bag[j++].valid = true;
        }
    }
    top = j;
    return;
}

void solve()
{
    scanf("%d",&m);
    getchar();
    int money = 0;
    top = 0;
    for(int i=0;i<6;i++)
    {
        bag[i].valid = bag[i].num = 0;
    }
    while(m--)
    {
        char c = getchar();
        gets(str);
        if(str[0] >= '0' && str[0] <= '9')
        {
            money += change(str);
        }
        else
        {
            if(c == '+')
            {
                bool flag = false;
                for(int i=0;i<n1;i++)
                {
                    if(strcmp(th[i].name , str) == 0)
                    {
                        flag = true;
                        if(money >= th[i].price)
                        {
                            if(top == 6) break;
                            strcpy(bag[top].name , str);
                            bag[top].num = 1;
                            bag[top].price = th[i].price;
                            bag[top].valid = true;
                            top++;
                            money -= th[i].price;
                        }
                        break;
                    }
                }
                if(flag) continue;
                for(int i=0;i<n2;i++)
                {
                    if(strcmp(com[i].name , str) == 0)
                    {
                        flag = true;
                        if(com[i].need > money) break;
                        bool have = true;
                        int c = 0;
                        for(int j=0;j<com[i].cnt;j++)
                        {
                            c += com[i].num[j];
                            int t = 0;
                            for(int k=0;k<top;k++)
                            {
                                if(strcmp(bag[k].name , com[i].dic[j]) == 0)
                                {
                                    t++;
                                }
                            }
                            if(t < com[i].num[j])
                            {
                                have = false;
                                break;
                            }
                        }
                        if(have && (top < 6 || c > 0))
                        {
                            money -= com[i].need;
                            int tot = com[i].need;
                            for(int j=0;j<com[i].cnt;j++)
                            {
                                int t = 0;
                                for(int k=0;k<top;k++)
                                {
                                    if(strcmp(bag[k].name , com[i].dic[j]) == 0 && bag[k].valid)
                                    {
                                        bag[k].valid = false;
                                        tot += bag[k].price;
                                        if(++t == com[i].num[j])
                                        {
                                            break;
                                        }
                                    }
                                }
                            }
                            for(int j=0;j<=top;j++)
                            {
                                if(bag[j].valid == false)
                                {
                                    bag[j].valid = true;
                                    bag[j].num = 1;
                                    strcpy(bag[j].name , com[i].name);
                                    bag[j].price = tot;
                                    if(j == top) top++;
                                    break;
                                }
                            }
                            update();
                        }
                        break;
                    }
                }
                if(flag) continue;
                for(int i=0;i<n3;i++)
                {
                    if(strcmp(consume[i].name , str) == 0)
                    {
                        flag = true;
                        if(money >= consume[i].price)
                        {
                            if(top == 6) break;
                            money -= consume[i].price;
                            bool have = false;
                            for(int j=0;j<top;j++)
                            {
                                if(strcmp(bag[j].name , str) == 0)
                                {
                                    have = true;
                                    bag[j].num++;
                                    bag[j].price += consume[i].price;
                                    break;
                                }
                            }
                            if(have == false)
                            {
                                strcpy(bag[top].name , str);
                                bag[top].num = 1;
                                bag[top].price = consume[i].price;
                                bag[top++].valid = true;
                            }
                        }
                        break;
                    }
                }
            }
            else
            {
                for(int i=0;i<top;i++)
                {
                    if(strcmp(bag[i].name , str) == 0)
                    {
                        bag[i].valid = false;
                        money += bag[i].price;
                        update();
                        break;
                    }
                }
            }
        }
    }
    sort(bag , bag + top);
    printf("%d\n%d\n",money,top);
    for(int i=0;i<top;i++)
    {
        printf("%s: %d\n",bag[i].name,bag[i].num);
    }
    puts("");
    return;
}

int main()
{
    while(~scanf("%d",&n1))
    {
        read();
        solve();
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/flying_stones_sure/article/details/7969446