解题报告
题目来源：
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
中文描述：
一个大家庭一起去电影院看电影，电影院有两种票提供：个人票和家庭票。个人票只允许一个人进电影院看电影，而家庭票则可允许一个人带上他的儿子或女儿一起去看电影。给出整个大家庭的家族树，让你算出整个大家庭一起去看电影的总费用以及买个人票和家庭票的数目。当存在有总费用相同的多种方案时，选取总票数最少的那个。
题目分析与算法模型
很显然，题目给出的简化版家谱是一棵树（每个家庭只有一个父亲或母亲），每个节点有三种情况：买个人票、买家庭票以及因为父母买了家庭票而不用买票。接着，我们对每一种情况分别讨论：
当某个节点买了个人票时，以这个节点为子树的最优情况（也就是最少费用）是：他的每个孩子的最优情况加上自己买的个人票。
当某个节点买了家庭票是，他的孩子可以选择买票，也可以选择不买票。对于他的每个孩子，这个节点会选择这个孩子买票时的最优情况和不买票的最优情况中的那个费用较低的那个（费用一样，就选总票数最少的那个），最后再加上自己的家庭票。
当某个节点因为父母买了家庭票而自己不需要买票时，他的最优情况是：他的每个孩子买票时的最优情况的总和。
无论当前节点选取的是什么情况，也无论这个节点会选取他的孩子的哪种情况，但肯定的是，只要当前节点在某种情况下（个人票、家庭票、不买票）达到最优，他的孩子也必然是某种情况下的最优。也就是，当原问题最优时，子问题也最优，因此问题具有最优子结构，而且在求解过程中，会多次计算某个节点在某种情况下的最优值，因此问题求解过程中具有重叠子问题。所以说，该问题可以用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中，比较常用的有string、vector、map、priority_queue等等，已经有一些做题经验的同学可以在平时顺带的看一下有关STL的内容（推荐一个网站：http://www.cplusplus.com/，里面几乎包含所有关于C++函数以及STL的参考资料，大部分函数都带有简明的代码样例）。