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];
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏逸鹏说道

临时处理小记:把Numpy的narray二进制文件转换成json文件

临时处理一个Numpy的二进制文件,分析知道里面是dict类型,简单小记一下,如果Numpy和Python基础不熟悉可以看我之前写的文章(贴一下Numpy的)

14130
来自专栏向治洪

java解决hash算法冲突

看了ConcurrentHashMap的实现, 使用的是拉链法. 虽然我们不希望发生冲突,但实际上发生冲突的可能性仍是存在的。当关键字值域远大于哈希表的长度...

26590
来自专栏数据结构与算法

洛谷P1731 [NOI1999]生日蛋糕(爆搜)

设从下往上数第i(1<=i<=M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i<M时,要求 R_i>R_{i+1}Ri​>Ri+1​ 且 H_i>H_{i+1}...

11010
来自专栏数据结构与算法

洛谷P1829 [国家集训队]Crash的数字表格 / JZPTAB(莫比乌斯反演)

今天的数学课上,Crash小朋友学习了最小公倍数(Least Common Multiple)。对于两个正整数a和b,LCM(a, b)表示能同时整除a和b的最...

15710
来自专栏Crossin的编程教室

【每周一坑】田忌赛马

本周的题目取自著名的历史典故:田忌赛马 背景资料如下 田忌经常与齐国众公子赛马,设重金赌注。田忌的上宾孙膑发现他们的马脚力都差不多,马分为上、中、下三等,于是对...

313100
来自专栏JAVA高级架构

程序员必须掌握的600个英语单词

11620
来自专栏一名叫大蕉的程序员

大数据计数原理1+0=1这你都不会算(二)No.50

上一次我们说完了用 HashSet 来进行计数了。我们可以发现,如果我们估计有N个数,那么我们至少需要N*32bit(按照int在32位操作系统下占用32个bi...

21180
来自专栏数据分析

[数据分析工具] Pandas 功能介绍(二)

条件过滤 我们需要看第一季度的数据是怎样的,就需要使用条件过滤 ? 体感的舒适适湿度是40-70,我们试着过滤出体感舒适湿度的数据 ? 最后整合上面两种条件,在...

37760
来自专栏海天一树

NOIP 2011初赛普及组C/C++答案详解

3 C 8G = 8 * 1024 M 8 * 1024 / 2 = 4096张 注意,题目说的是“大约”,不要求精确。

17820
来自专栏落影的专栏

程序员进阶之算法练习(八)附两道搜狐笔试题

前言 前面讲了那么多算法的重要性。口说无凭,这次带上两道搜狐今年的笔试题。 这里先附上两道搜狐题目的大意: 题目一: 《宝石》 有一串宝石首尾相连,用...

44050

扫码关注云+社区

领取腾讯云代金券