POJ PKU Let's Go to the Movies 解题报告
题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=3513
题目大意是输入树状的家庭关系，问怎么买票（买家庭票还是个人票）最省钱并且票的数量最少
这道题是一道Hash+树状DP问题。编码长度相当可观，需要较好的编码能力
我这题编码就犯了几个低级错误，然后算法错误一次，导致了无数的WA
先给几组测试数据
2 3
a b
b c
c d
2 3
a b c
b d e
c f g
d h i
e j k
f l m
g n o
1 3
a b c d e
f g h i j a n k l
n m o p q
0 0答案是：
1. 0 2 6
2. 0 5 15
3. 0 3 9贴代码(注意下代码是C++的。由于使用了 cin和cout，G++有输入优化会降低cin和cout的时间，如果用G++要把cin和cout改成scanf和printf，然后少用string，否则会TLE)：
/**
* Author: OWenT
* POJ PKU 3513 Let's Go to the Movies
* http://acm.pku.edu.cn/JudgeOnline/problem?id=3513
* 树形DP + Hash
* WA了好多次
*/
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define MAXN 100005
typedef struct
{
vector<long>chirldren;
bool isPF;
long m_t,m_s,m_f;
char tt;
}node;
node glo[MAXN];
map<string, long>hash;
long nodeNum;
void check(long pos, long &ns, long &nf, long &t, long &s, long &f);
void checkChirld(long pos, long &ns, long &nf, long &t, long &s, long &f);
void initNode(long &pos);
int main()
{
//freopen("d:\\movies.in.txt","r",stdin);
//freopen("d:\\movies.out.txt","w",stdout);
long s,f, k = 0;
long ns,nf,t;
long tmpPos1,tmpPos2, i;
string str;
while(cin>> str)
{
if(str[0] <= '9' && str[0] >= '0')
{
//处理数据
if(k)
{
for(i = 0; i < nodeNum; i ++)
if(glo[i].isPF)
check(i, ns, nf, t, s, f);
//输出
printf("%ld. %ld %ld %ld\n", k, ns, nf, t);
}
//下一组数据
k ++;
ns = nf = t = nodeNum = 0;
cin>> f;
s = atol(str.c_str());
if(!s && !f)
break;
hash.clear();
}
else
{
//父节点映射
if(hash.find(str) == hash.end())
{
initNode(nodeNum);
hash[str] = nodeNum;
tmpPos1 = nodeNum ++;
}
else
tmpPos1 = hash[str];
//子节点映射
while(getchar() != '\n')
{
cin>> str;
if(hash.find(str) == hash.end())
{
initNode(nodeNum);
hash[str] = nodeNum;
tmpPos2 = nodeNum ++;
}
else
tmpPos2 = hash[str];
glo[tmpPos1].chirldren.push_back(tmpPos2);
glo[tmpPos2].isPF = false;
}
}
}
return 0;
}
void check(long pos, long &ns, long &nf, long &t, long &s, long &f)
{
//0为当前个人票数据，1为当前家庭票数据
long tns[2] = {1, 0},
tnf[2] = {0, 1},
tt[2] = {s, f};
long i, n = 0;
if(glo[pos].m_t >= 0)
{
ns += glo[pos].m_s;
nf += glo[pos].m_f;
t += glo[pos].m_t;
return;
}
for(i = 0; i < glo[pos].chirldren.size(); i ++)
check(glo[pos].chirldren[i], tns[0], tnf[0], tt[0], s, f);//当前个人票的结果
checkChirld(pos, tns[1], tnf[1], tt[1], s, f);//当前家庭票的结果
if(tt[0] < tt[1] || (tt[0] == tt[1] && tns[0] + tnf[0] <= tns[1] + tnf[1]))
{
t += tt[0];
ns += tns[0];
nf += tnf[0];
glo[pos].m_f = tnf[0];
glo[pos].m_s = tns[0];
glo[pos].m_t = tt[0];
glo[pos].tt = 's';
}
else
{
t += tt[1];
ns += tns[1];
nf += tnf[1];
glo[pos].m_f = tnf[1];
glo[pos].m_s = tns[1];
glo[pos].m_t = tt[1];
glo[pos].tt = 'f';
}
//printf("ID:%ld: f:%ld s:%ld t:%ld TicketType: %c\n", pos, glo[pos].m_f, glo[pos].m_s, glo[pos].m_t, glo[pos].tt);
}
void initNode(long &pos)
{
glo[pos].isPF = true;
glo[pos].chirldren.clear();
glo[pos].m_f = glo[pos].m_s = glo[pos].m_t = -1;
}
void checkChirld(long pos, long &ns, long &nf, long &t, long &s, long &f)
{
long i, j, k, l;
long len1, len2;
long tns[2],tnf[2],tt[2];
len1 = glo[pos].chirldren.size();
for(i = 0; i < len1; i ++)
{
k = glo[pos].chirldren[i];
tns[0] = glo[ k ].m_s;
tnf[0] = glo[ k ].m_f;
tt[0] = glo[ k ].m_t;
tns[1] = 0;
tnf[1] = 0;
tt[1] = 0;
len2 = glo[ k ].chirldren.size();
for(j = 0; j < len2; j ++)
{
l = glo[k].chirldren[j];
check(l, tns[1], tnf[1], tt[1], s, f);
}
if(tt[0] < tt[1] || (tt[0] == tt[1] && tns[0] + tnf[0] <= tns[1] + tnf[1]))
{
t += tt[0];
ns += tns[0];
nf += tnf[0];
}
else
{
t += tt[1];
ns += tns[1];
nf += tnf[1];
}
}
}Last updated