hdu 2677

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

思路：一开始没思路，看大牛一博客也的。。。orz....为了方便处理给每一个装备一个标号，并记录价格和拥有数量，买不到的装备价格用一个特殊的数标记，然后对需要的装备进行递归处理，对于一件装备，如果已经拥有就直接用，如果没有就买，如果买不到就合成。数据保证需要的装备肯定能得到。

View Code

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<string>
  5 #include<queue>
  6 #include<vector>
  7 using namespace std;
  8 #define MAXN 222
  9 #define inf 1<<30
 10 struct Node{
 11     string name;
 12     int price,num;
 13 }node[MAXN];
 14 int n,m,x,k;
 15 string str;
 16 vector<int>vet[MAXN];
 17 
 18 int Find(string &str){
 19     for(k=0;k<m;k++){
 20         if(node[k].name==str)break;
 21     }
 22     if(k<m)return k;
 23     node[m].name=str;
 24     node[m].num=0;
 25     node[m++].price=inf;
 26     return m-1;
 27 }
 28 
 29 
 30 int Solve(int x,int num){
 31     if(num<=node[x].num){
 32         node[x].num-=num;
 33         return 0;
 34     }else {
 35         num-=node[x].num;
 36         node[x].num=0;
 37         
 38         if(node[x].price!=inf){
 39             return node[x].price*num;//说明商店中是买的到的
 40         }else {
 41             //不可以买到的商品就要合成了。
 42             int ans=0;
 43             for(int i=0;i<vet[x].size();i++){
 44                 ans+=Solve(vet[x][i],num);
 45             }
 46             return ans;
 47         }
 48     }
 49 }
 50 
 51 
 52 int main(){
 53     while(~scanf("%d",&n)){
 54         queue<int>Q;
 55         for(int i=0;i<MAXN;i++)vet[i].clear();
 56         for(int i=0;i<n;i++){
 57             cin>>node[i].name>>node[i].price;
 58             node[i].num=0;
 59         }
 60         m=n;
 61         scanf("%d",&n);
 62         for(int i=0;i<n;i++){
 63             cin>>str>>x;
 64             for(k=0;k<m;k++){
 65                 if(str==node[k].name)break;
 66             }
 67             if(k==m){
 68                 node[m].name=str;
 69                 node[m].num=x;
 70                 node[m++].price=inf;
 71             }else 
 72                 node[k].num+=x;
 73         }
 74         scanf("%d",&n);
 75         while(n--){
 76             cin>>str;
 77             Q.push(Find(str));
 78             cin>>str;
 79             while(str!="="){
 80                 cin>>str;
 81                 Q.push(Find(str));
 82                 cin>>str;
 83             }
 84             cin>>str;
 85             x=Find(str);
 86             while(!Q.empty()){
 87                 int y=Q.front();
 88                 Q.pop();
 89                 vet[x].push_back(y);
 90             }
 91         }
 92         scanf("%d",&n);
 93         int ans=0;
 94         while(n--){
 95             cin>>str>>x;
 96             ans+=Solve(Find(str),x);
 97         }
 98         printf("%d\n",ans);
 99     }
100     return 0;
101 }