青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

QuXiao

每天進步一點點!

  C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理 ::
  50 隨筆 :: 0 文章 :: 27 評論 :: 0 Trackbacks

解題報告

 

題目來源:

PKU 3513 Let's Go to the Movies

 

分類:

樹形DP

 

原文:

Let's Go to the Movies

 

Time Limit: 1000MS


Memory Limit: 65536K

Total Submissions: 228


Accepted: 56

Description

http://acm.pku.edu.cn/JudgeOnline/images/3513_1.pngA favorite pastime for big families in Acmestan is going to the movies. It is quite common to see a number of these multi-generation families going together to watch a movie. Movie theaters in Acmestan have two types of tickets: A single ticket is for exactly one person while a family ticket allows a parent and their children to enter the theater. Needless to say, a family ticket is always priced higher than a single ticket, sometimes as high as five times the price of a single ticket.

It is quite challenging for families to decide which ticket arrangement is most economical to buy. For example, the family depicted in the figure on the right has four ticket arrangements to choose from: Seven single tickets; Two family tickets; One family ticket (for adam, bob, cindy) plus four single tickets for the rest; Or, one family ticket (for bob and his four children) plus single tickets for the remaining two.

Write a program to determine which ticket arrangement has the least price. If there are more than one such arrangement, print the arrangement that has the least number of tickets.

Input

Your program will be tested on one or more test cases. The first line of each test case includes two positive integers (S and F) where S is the price of a single ticket and F is the price of a family ticket. The remaining lines of the test case are either the name of a person going by him/herself, or of the form:

N1 N2 N3Nk

where N1 is the name of a parent, with N2Nk being his/her children. Names are all lower-case letters, and no longer than 1000 characters. No parent will be taking more than 1000 of their children to the movies :-). Names are unique, the name of a particular person will appear at most twice: Once as a parent, and once as a child. There will be at least one person and at most 100,000 people in any test case.

The end of a test case is identified by the beginning of the following test case (a line made of two integers.) The end of the last test case is identified by two zeros.

Output

For each test case, write the result using the following format:

k. NS NF T

Where k is the test case number (starting at 1), NS is the number of single tickets, NF is the number of family tickets, and T is the total cost of tickets.

Sample Input

1 3

adam bob cindy

bob dima edie fairuz gary

1 2

john

paul

george

ringo

1 3

a b c

0 0

Sample Output

1. 2 1 5

2. 4 0 4

3. 0 1 3

Source

Arab and North Africa 2007

 

 

中文描述:

一個大家庭一起去電影院看電影,電影院有兩種票提供:個人票和家庭票。個人票只允許一個人進電影院看電影,而家庭票則可允許一個人帶上他的兒子或女兒一起去看電影。給出整個大家庭的家族樹,讓你算出整個大家庭一起去看電影的總費用以及買個人票和家庭票的數目。當存在有總費用相同的多種方案時,選取總票數最少的那個。

 

題目分析與算法模型

很顯然,題目給出的簡化版家譜是一棵樹(每個家庭只有一個父親或母親),每個節點有三種情況:買個人票、買家庭票以及因為父母買了家庭票而不用買票。接著,我們對每一種情況分別討論:

當某個節點買了個人票時,以這個節點為子樹的最優情況(也就是最少費用)是:他的每個孩子的最優情況加上自己買的個人票。

當某個節點買了家庭票是,他的孩子可以選擇買票,也可以選擇不買票。對于他的每個孩子,這個節點會選擇這個孩子買票時的最優情況和不買票的最優情況中的那個費用較低的那個(費用一樣,就選總票數最少的那個),最后再加上自己的家庭票。

當某個節點因為父母買了家庭票而自己不需要買票時,他的最優情況是:他的每個孩子買票時的最優情況的總和。

無論當前節點選取的是什么情況,也無論這個節點會選取他的孩子的哪種情況,但肯定的是,只要當前節點在某種情況下(個人票、家庭票、不買票)達到最優,他的孩子也必然是某種情況下的最優。也就是,當原問題最優時,子問題也最優,因此問題具有最優子結構,而且在求解過程中,會多次計算某個節點在某種情況下的最優值,因此問題求解過程中具有重疊子問題。所以說,該問題可以用DP來解決。

 

代碼:

#include <iostream>

#include <string>

#include <map>

#include <vector>

using namespace std;

 

const int MAX = 100005;

 

int single, family;

int a, b;               //暫時記錄個人票和家庭票的價格

map<string, int> dic;   //將名字與一數字進行映射

map<string, int>::iterator it;          //迭代器

vector<int> sons[MAX];  //鄰接表,記錄某個節點的孩子

int people;             //家庭中的人數

int notRoot[MAX];

char s[1005];           //暫時存儲輸入的姓名

 

struct Node

{                 

   int singleNum, familyNum;

   int minPrice;

};

//某個節點買票時的最優情況和不買票時的最優情況

Node minBuy[MAX], minNotBuy[MAX];

 

int isNumber (string s)

{

   int i, ans;

   ans = 0;

   for (i=0; i<s.length(); i++)

   {

        if ( s[i] >= '0' && s[i] <= '9' )

              ans = ans*10 + (s[i]-'0');

        else

              return -1;

   }

   return ans;

}

 

void Initial ()

{

   memset(notRoot, 0, sizeof(notRoot));

   people = 0;

   memset(minBuy, -1, sizeof(minBuy));

   memset(minNotBuy, -1, sizeof(minNotBuy));

   dic.clear();

}

 

bool Input ()

{

   //如果上個testcase已經將這次輸入的第一個變量讀入到a,就無需再讀入

   if ( a == -1 )

        scanf("%d", &a);

   scanf("%d", &b);

   single = a;

   family = b;

   a = b = -1;

   if ( single == 0 && family == 0 )

        return false;

 

   char ch;

   int pIndex, sIndex;

   string parent, son;

  

   Initial ();

 

   while (1)

   {

        //先將名字讀入字符串數組,在將其置于string, 這樣做是為了節省時間

        scanf("%s", &s);          

        parent = "";

        parent.append(s);

        a = isNumber(parent);

        if ( a != -1 )       //讀入了下個testcase的數據

              break;

 

        it = dic.find(parent);     //查找有無對應映射

        if ( it ==  dic.end() )

        {

              dic[parent] = people;

              sons[people].clear();

              people++;

        }

 

        pIndex = dic[parent];

 

        //讀取當前節點的孩子

        ch = getchar();

        while ( ch != '\n' )

        {

              scanf("%s", &s);

              son = "";

              son.append(s);       //把字符數組的內容傳給string

              it = dic.find(son);

              if ( it == dic.end() )

              {

                   dic[son] = people;

                   sons[people].clear();

                   people++;

              }

              sIndex = dic[son];

              sons[pIndex].push_back(sIndex);

              notRoot[sIndex] = 1;

 

              ch = getchar();

        }

   }

 

   return true;

}

 

int getMinBuy (int);          //計算買票時的最少費用

int getMinNotBuy (int);       //計算不買票時的最少費用

 

int getMinBuy (int index)

{

   if ( minBuy[index].minPrice != -1 )

        return minBuy[index].minPrice;

 

   int i;

   //當前節點買家庭票

   int singleNum1, familyNum1, price1;

   singleNum1 = 0;

   familyNum1 = 1;

   price1 = family;

   for (i=0; i<sons[index].size(); i++)

   {

        //買票時的費用比不買票時的費用低,或者費用相同時,買票時所買的總票數少

        if ( getMinBuy(sons[index][i]) < getMinNotBuy(sons[index][i])

        || ( getMinBuy(sons[index][i])==getMinNotBuy(sons[index][i])

&& minBuy[sons[index][i]].singleNum+

   minBuy[sons[index][i]].familyNum

   <=

   minNotBuy[sons[index][i]].singleNum +     

   minNotBuy[sons[index][i]].familyNum ) )

        {

              price1 += minBuy[sons[index][i]].minPrice;

              singleNum1 += minBuy[sons[index][i]].singleNum;

              familyNum1 += minBuy[sons[index][i]].familyNum;

        }

        else

        {

              price1 += minNotBuy[sons[index][i]].minPrice;

              singleNum1 += minNotBuy[sons[index][i]].singleNum;

              familyNum1 += minNotBuy[sons[index][i]].familyNum;

        }

   }

 

   //當前節點買個人票

   int singleNum2, familyNum2, price2;

   singleNum2 = 1;

   familyNum2 = 0;

   price2 = single;

   for (i=0; i<sons[index].size(); i++)

   {

        price2 += getMinBuy(sons[index][i]);

        singleNum2 += minBuy[sons[index][i]].singleNum;

        familyNum2 += minBuy[sons[index][i]].familyNum;

   }

   //決定當前節點買票時,是買個人票還是買家庭票

   if ( price1 < price2 || ( price1 == price2 && singleNum1 +

        familyNum1 <= singleNum2 + familyNum2 ) )

   {

        minBuy[index].minPrice = price1;

        minBuy[index].singleNum = singleNum1;

        minBuy[index].familyNum = familyNum1;

   }

   else

   {

        minBuy[index].minPrice = price2;

        minBuy[index].singleNum = singleNum2;

        minBuy[index].familyNum = familyNum2;

   }

 

   return minBuy[index].minPrice;

}

 

int getMinNotBuy (int index)

{

   if ( minNotBuy[index].minPrice != -1 )

        return minNotBuy[index].minPrice;

 

   int i, singleNum, familyNum, price;

   singleNum = familyNum = 0;

   price = 0;

   //取每個孩子買票的最優情況

   for (i=0; i<sons[index].size(); i++)

   {

        price += getMinBuy(sons[index][i]);

        singleNum += minBuy[sons[index][i]].singleNum;

        familyNum += minBuy[sons[index][i]].familyNum;

   }

 

   minNotBuy[index].minPrice = price;

   minNotBuy[index].singleNum = singleNum;

   minNotBuy[index].familyNum = familyNum;

   return minNotBuy[index].minPrice;

}

 

void Solve ()

{

 

   int i, price, singleNum, familyNum;

   price = singleNum = familyNum = 0;

 

   for (i=0; i<people; i++)

   {

        if ( ! notRoot[i] )

        {

              price += getMinBuy(i);

              singleNum += minBuy[i].singleNum;

              familyNum += minBuy[i].familyNum;

        }

   }

 

   printf("%d %d %d\n", singleNum, familyNum, price);

}

 

int main ()

{

   int i = 0;

   a = b = -1;

   while ( Input() )

   {

        printf("%d. ", ++i);

        Solve ();

   }

   return 0;

}

 

心得:

本題有兩個考察的地方,一是是否能對簡單的樹形DP模型進行構建,二是是否有比較強的實際編程能力。第一點我不想再重復,前面講的也比較詳細。做了這題,感覺收獲最大的就是學了不少的編程的小技巧。比如處理輸入輸出(本題的輸入讓人有些頭疼)、利用STL中的map把字符串和整數映射起來(這個很有用)、利用vector建樹、為了節省時間先把字符串讀入到字符數組,再把內容傳給string等等。雖然這些小技巧看起來有些“微不足道”,但在平時做題或者比賽時,如果不熟練掌握這些小技巧,往往會在關鍵時刻阻礙你解題的步伐。算法的理論知識是可以從書本上學到的,但那些編程的技巧卻只能從平時做題的積累中才能慢慢掌握的。其中,我感覺,使用STL可以大大減少編程的復雜程度。雖然對于那些剛接觸算法的同學來說,我并不推薦使用STL,因為這樣會屏蔽掉許多底層的原理。但在比賽時,使用STL還是可以節約不少時間與精力的。STL中,比較常用的有stringvector、map、priority_queue等等,已經有一些做題經驗的同學可以在平時順帶的看一下有關STL的內容(推薦一個網站:http://www.cplusplus.com/,里面幾乎包含所有關于C++函數以及STL的參考資料,大部分函數都帶有簡明的代碼樣例)。

posted on 2008-03-25 23:16 quxiao 閱讀(575) 評論(0)  編輯 收藏 引用 所屬分類: ACM
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            国产日本欧洲亚洲| 欧美电影免费观看高清| 国产精品久久久免费| 亚洲尤物精选| 亚洲欧美日韩久久精品 | 一区二区三区三区在线| 国产精品第三页| 久久久国产午夜精品| 久久国产99| 亚洲精品久久久久久久久| 亚洲精品日日夜夜| 国产欧美精品在线观看| 麻豆91精品| 欧美日韩亚洲网| 久久成人免费电影| 欧美 日韩 国产在线| 亚洲图中文字幕| 欧美在线一区二区| 亚洲国产一区二区精品专区| 亚洲免费成人| 韩日成人在线| 亚洲精品一级| 国内精品视频在线播放| 亚洲欧洲在线视频| 国产日韩精品在线| 91久久精品日日躁夜夜躁国产| 国产精品美女久久久| 蜜臀av在线播放一区二区三区| 欧美啪啪一区| 美女脱光内衣内裤视频久久影院| 欧美日韩国产亚洲一区| 久久久久久久久久久成人| 欧美女同在线视频| 老司机精品导航| 国产精品久久久一区二区| 欧美激情视频在线免费观看 欧美视频免费一 | 久久九九国产精品怡红院| 亚洲精品一品区二品区三品区| 亚洲尤物精选| 一级成人国产| 久久综合狠狠综合久久综青草 | 日韩视频一区二区在线观看 | 国产日韩在线看| 亚洲精品一二三| 亚洲国产精品久久久久| 亚洲欧美日韩精品久久亚洲区| 一本久久综合亚洲鲁鲁| 久久综合九色综合久99| 欧美一区二区啪啪| 欧美日韩一区二区在线视频 | 99国产精品视频免费观看一公开| 悠悠资源网亚洲青| 欧美在线亚洲| 久久久久免费| 国产亚洲欧洲一区高清在线观看 | 久久久久国产免费免费| 欧美在线啊v一区| 国产精品爽黄69| 在线一区二区三区做爰视频网站| 亚洲精选视频免费看| 欧美99久久| 亚洲福利在线观看| 亚洲伦理在线观看| 欧美精品自拍| 亚洲美女av电影| 亚洲无亚洲人成网站77777| 欧美激情一区在线| 亚洲精品你懂的| 亚洲人午夜精品免费| 欧美jizzhd精品欧美巨大免费| 欧美成人午夜激情| 亚洲精品中文在线| 欧美日韩在线直播| 亚洲欧美日韩精品久久奇米色影视| 亚洲欧美在线网| 国产欧美一区在线| 久久精品国内一区二区三区| 久久在线播放| 亚洲免费观看在线视频| 欧美色大人视频| 亚洲综合三区| 久久综合五月| 日韩写真视频在线观看| 欧美香蕉大胸在线视频观看| 在线综合+亚洲+欧美中文字幕| 午夜电影亚洲| 一区二区亚洲精品国产| 欧美大片一区二区| 一区二区三区高清视频在线观看| 性做久久久久久久免费看| 激情文学综合丁香| 欧美日本韩国一区| 欧美亚洲自偷自偷| 亚洲国产mv| 亚洲欧美日韩爽爽影院| 极品中文字幕一区| 欧美日韩一级大片网址| 欧美一级大片在线观看| 91久久精品www人人做人人爽| 午夜精品久久久久99热蜜桃导演| 黄色资源网久久资源365| 欧美成人有码| 香蕉久久a毛片| 91久久在线| 另类av一区二区| 亚洲一本视频| 亚洲高清在线精品| 国产欧美一区二区三区国产幕精品| 久久久久国产精品一区三寸| 99re成人精品视频| 欧美福利专区| 久久九九精品| 亚洲伊人一本大道中文字幕| 在线观看国产精品网站| 国产片一区二区| 欧美日韩无遮挡| 老司机亚洲精品| 午夜视频久久久久久| 一级成人国产| 亚洲国产欧美一区| 久久久夜色精品亚洲| 亚洲欧美激情四射在线日 | 亚洲欧美日韩在线综合| 亚洲国产成人av| 免费一级欧美片在线观看| 亚洲欧美日韩区| 亚洲一区二区三区视频| 亚洲精品日本| 亚洲欧洲三级| 亚洲三级免费观看| 在线观看亚洲精品视频| 国产一区二区视频在线观看 | 欧美日韩情趣电影| 美女主播一区| 另类图片综合电影| 久久久久国产精品麻豆ai换脸| 亚洲欧美国产三级| 亚洲自拍偷拍网址| 亚洲女女女同性video| 中文国产成人精品| 国产精品99久久久久久人| 亚洲作爱视频| 亚洲视屏在线播放| 亚洲尤物精选| 欧美综合国产精品久久丁香| 欧美一区二区三区视频在线| 性欧美xxxx视频在线观看| 欧美一区二区三区喷汁尤物| 欧美在线视频在线播放完整版免费观看 | 亚洲色诱最新| 午夜精品国产更新| 久久精品女人天堂| 久久一区亚洲| 亚洲国产精品成人va在线观看| 亚洲第一精品影视| av成人手机在线| 亚洲免费一级电影| 久久激情综合| 欧美jizz19性欧美| 欧美性事免费在线观看| 国产亚洲免费的视频看| 在线电影院国产精品| 亚洲免费av网站| 欧美一激情一区二区三区| 久久久国产视频91| 亚洲国产日韩一区二区| 在线一区二区三区四区| 欧美在线三级| 欧美激情第三页| 国产精品午夜久久| 伊人婷婷久久| 亚洲综合三区| 老牛影视一区二区三区| 99国产精品| 久久精品九九| 欧美三级特黄| 在线观看日韩| 亚洲欧美激情一区| 欧美高清视频在线播放| 一区二区三区高清在线观看| 久久久久国产精品一区二区| 欧美三级精品| 亚洲高清av| 性高湖久久久久久久久| 男女精品网站| 亚洲一区精品视频| 欧美大秀在线观看| 红桃视频国产一区| 亚洲一区二区三区乱码aⅴ蜜桃女| 久久久噜噜噜久久狠狠50岁| 亚洲免费不卡| 欧美福利电影网| 国产一区二区0| 亚洲制服欧美中文字幕中文字幕| 久久噜噜噜精品国产亚洲综合| 亚洲麻豆av| 欧美大片网址| 91久久在线观看| 久久久久久网站| 亚洲欧美在线播放|