解題報(bào)告
題目來源：
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
A 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 N3
… Nk
where N1
is the name of a parent, with N2… Nk 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
中文描述：
一個(gè)大家庭一起去電影院看電影，電影院有兩種票提供：個(gè)人票和家庭票。個(gè)人票只允許一個(gè)人進(jìn)電影院看電影，而家庭票則可允許一個(gè)人帶上他的兒子或女兒一起去看電影。給出整個(gè)大家庭的家族樹，讓你算出整個(gè)大家庭一起去看電影的總費(fèi)用以及買個(gè)人票和家庭票的數(shù)目。當(dāng)存在有總費(fèi)用相同的多種方案時(shí)，選取總票數(shù)最少的那個(gè)。
題目分析與算法模型
很顯然，題目給出的簡(jiǎn)化版家譜是一棵樹（每個(gè)家庭只有一個(gè)父親或母親），每個(gè)節(jié)點(diǎn)有三種情況：買個(gè)人票、買家庭票以及因?yàn)楦改纲I了家庭票而不用買票。接著，我們對(duì)每一種情況分別討論：
當(dāng)某個(gè)節(jié)點(diǎn)買了個(gè)人票時(shí)，以這個(gè)節(jié)點(diǎn)為子樹的最優(yōu)情況（也就是最少費(fèi)用）是：他的每個(gè)孩子的最優(yōu)情況加上自己買的個(gè)人票。
當(dāng)某個(gè)節(jié)點(diǎn)買了家庭票是，他的孩子可以選擇買票，也可以選擇不買票。對(duì)于他的每個(gè)孩子，這個(gè)節(jié)點(diǎn)會(huì)選擇這個(gè)孩子買票時(shí)的最優(yōu)情況和不買票的最優(yōu)情況中的那個(gè)費(fèi)用較低的那個(gè)（費(fèi)用一樣，就選總票數(shù)最少的那個(gè)），最后再加上自己的家庭票。
當(dāng)某個(gè)節(jié)點(diǎn)因?yàn)楦改纲I了家庭票而自己不需要買票時(shí)，他的最優(yōu)情況是：他的每個(gè)孩子買票時(shí)的最優(yōu)情況的總和。
無論當(dāng)前節(jié)點(diǎn)選取的是什么情況，也無論這個(gè)節(jié)點(diǎn)會(huì)選取他的孩子的哪種情況，但肯定的是，只要當(dāng)前節(jié)點(diǎn)在某種情況下（個(gè)人票、家庭票、不買票）達(dá)到最優(yōu)，他的孩子也必然是某種情況下的最優(yōu)。也就是，當(dāng)原問題最優(yōu)時(shí)，子問題也最優(yōu)，因此問題具有最優(yōu)子結(jié)構(gòu)，而且在求解過程中，會(huì)多次計(jì)算某個(gè)節(jié)點(diǎn)在某種情況下的最優(yōu)值，因此問題求解過程中具有重疊子問題。所以說，該問題可以用DP來解決。
代碼：
#include <iostream>
#include <string>
#include <map>
#include <vector>
using namespace std;
const int MAX = 100005;
int single, family;
int a, b; //暫時(shí)記錄個(gè)人票和家庭票的價(jià)格
map<string, int> dic; //將名字與一數(shù)字進(jìn)行映射
map<string, int>::iterator it; //迭代器
vector<int> sons[MAX]; //鄰接表，記錄某個(gè)節(jié)點(diǎn)的孩子
int people; //家庭中的人數(shù)
int notRoot[MAX];
char s[1005]; //暫時(shí)存儲(chǔ)輸入的姓名
struct Node
{
int singleNum, familyNum;
int minPrice;
};
//某個(gè)節(jié)點(diǎn)買票時(shí)的最優(yōu)情況和不買票時(shí)的最優(yōu)情況
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 ()
{
//如果上個(gè)testcase已經(jīng)將這次輸入的第一個(gè)變量讀入到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)
{
//先將名字讀入字符串?dāng)?shù)組，在將其置于string， 這樣做是為了節(jié)省時(shí)間
scanf("%s",
&s);
parent = "";
parent.append(s);
a = isNumber(parent);
if ( a != -1 ) //讀入了下個(gè)testcase的數(shù)據(jù)
break;
it = dic.find(parent); //查找有無對(duì)應(yīng)映射
if ( it == dic.end() )
{
dic[parent] = people;
sons[people].clear();
people++;
}
pIndex = dic[parent];
//讀取當(dāng)前節(jié)點(diǎn)的孩子
ch = getchar();
while ( ch != '\n' )
{
scanf("%s",
&s);
son = "";
son.append(s); //把字符數(shù)組的內(nèi)容傳給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); //計(jì)算買票時(shí)的最少費(fèi)用
int getMinNotBuy (int); //計(jì)算不買票時(shí)的最少費(fèi)用
int getMinBuy (int index)
{
if ( minBuy[index].minPrice !=
-1 )
return
minBuy[index].minPrice;
int i;
//當(dāng)前節(jié)點(diǎn)買家庭票
int singleNum1, familyNum1,
price1;
singleNum1 = 0;
familyNum1 = 1;
price1 = family;
for (i=0;
i<sons[index].size(); i++)
{
//買票時(shí)的費(fèi)用比不買票時(shí)的費(fèi)用低，或者費(fèi)用相同時(shí)，買票時(shí)所買的總票數(shù)少
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;
}
}
//當(dāng)前節(jié)點(diǎn)買個(gè)人票
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;
}
//決定當(dāng)前節(jié)點(diǎn)買票時(shí)，是買個(gè)人票還是買家庭票
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;
//取每個(gè)孩子買票的最優(yōu)情況
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;
}
心得：
本題有兩個(gè)考察的地方，一是是否能對(duì)簡(jiǎn)單的樹形DP模型進(jìn)行構(gòu)建，二是是否有比較強(qiáng)的實(shí)際編程能力。第一點(diǎn)我不想再重復(fù)，前面講的也比較詳細(xì)。做了這題，感覺收獲最大的就是學(xué)了不少的編程的小技巧。比如處理輸入輸出（本題的輸入讓人有些頭疼）、利用STL中的map把字符串和整數(shù)映射起來（這個(gè)很有用）、利用vector建樹、為了節(jié)省時(shí)間先把字符串讀入到字符數(shù)組，再把內(nèi)容傳給string等等。雖然這些小技巧看起來有些“微不足道”，但在平時(shí)做題或者比賽時(shí)，如果不熟練掌握這些小技巧，往往會(huì)在關(guān)鍵時(shí)刻阻礙你解題的步伐。算法的理論知識(shí)是可以從書本上學(xué)到的，但那些編程的技巧卻只能從平時(shí)做題的積累中才能慢慢掌握的。其中，我感覺，使用STL可以大大減少編程的復(fù)雜程度。雖然對(duì)于那些剛接觸算法的同學(xué)來說，我并不推薦使用STL，因?yàn)檫@樣會(huì)屏蔽掉許多底層的原理。但在比賽時(shí)，使用STL還是可以節(jié)約不少時(shí)間與精力的。STL中，比較常用的有string、vector、map、priority_queue等等，已經(jīng)有一些做題經(jīng)驗(yàn)的同學(xué)可以在平時(shí)順帶的看一下有關(guān)STL的內(nèi)容（推薦一個(gè)網(wǎng)站：http://www.cplusplus.com/，里面幾乎包含所有關(guān)于C++函數(shù)以及STL的參考資料，大部分函數(shù)都帶有簡(jiǎn)明的代碼樣例）。