2 shunfurh shunfurh 于 2017.01.05 15:31 提问

一个纸牌集合的相关问题

问题描述 :

In Card Captor Sakura, Sakura is a lovely girl. One day, she opens a magic box containing many cards. Every card has a respective natural force in the real world, such as wind, water, YY, LMY, and so on. Suddenly a gust of wind blows away these cards. Sakura only has a card called “THE_WINDY” in her hand. Sakura knows if any card is not found, disaster comes. So she must collect all the cards. Cards can only be collected one by one. Suppose there are N cards to be collected. It takes Ti to collect the ith card, 1≤i≤N. For the ith card, there is a corresponding card Pi. If card Pi has been collected, it only takes time ti to collect the ith card, where ti<Ti.

Your task is to help Sakura design a schedule that takes the shortest time to collect all cards.

输入:

The input consists of several test cases. Each test case starts with a line giving the number N of cards (1≤N≤100). Each of the next N lines describes a card.

Every card has the format: Name1 Ti Name2 ti, where Name1 and Name2 are cards’ names, consisting of uppercase letters and underlines. The length of cards’ names is no more than 20 characters. Card Name1 is a card to be collected. It takes Ti to collect Card Name1 without Card Name2. And it takes ti to collect Card Name1 with Card Name2, where ti<Ti.

End of input is indicated by a line consisting of a single 0.

输出:

The input consists of several test cases. Each test case starts with a line giving the number N of cards (1≤N≤100). Each of the next N lines describes a card.

Every card has the format: Name1 Ti Name2 ti, where Name1 and Name2 are cards’ names, consisting of uppercase letters and underlines. The length of cards’ names is no more than 20 characters. Card Name1 is a card to be collected. It takes Ti to collect Card Name1 without Card Name2. And it takes ti to collect Card Name1 with Card Name2, where ti<Ti.

End of input is indicated by a line consisting of a single 0.

样例输入:

5
THE_FLY 67 THE_WINDY 39
THE_SHADOW 97 THE_WINDY 49
THE_WATER 139 THE_FLY 69
THE_RAIN 37 THE_WATER 18
THE_WOOD 5 THE_RAIN 1
1
THE_LOOP 35 THE_LOOP 25
0
样例输出:

176
35

1个回答

caozhy
caozhy   Ds   Rxr 2017.01.12 00:47
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
纸牌博弈问题
题目: 题目:有一个整型数组A,代表数值不同的纸牌排成一条线。玩家a和玩家b依次拿走每张纸牌,规定玩家a先拿,玩家b后拿, 但是每个玩家每次只能拿走最左或最右的纸牌,玩家a和玩家b都绝顶聪明,他们总会采用最优策略。请返回最后获胜者的分数。 给定纸牌序列A及序列的大小n,请返回最后分数较高者得分数(相同则返回任意一个分数)。 测试样例: [1,2,100,4],4 返回:101 解
动态规划-排成一条线的纸牌博弈等问题
有一个整型数组A,代表数值不同的纸牌排成一条线。玩家a和玩家b依次拿走每张纸牌,规定玩家a先拿,玩家B后拿,但是每个玩家每次只能拿走最左或最右的纸牌,玩家a和玩家b都绝顶聪明,他们总会采用最优策略。请返回最后获胜者的分数。 给定纸牌序列A及序列的大小n,请返回最后分数较高者得分数(相同则返回任意一个分数)。保证A中的元素均小于等于1000。且A的大小小于等于300。 测试样例: [1,2,1
D 1045: [HAOI2008] 糖果传递 (环状的均分纸牌)
Description 有n个小朋友坐成一圈,每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。 Input 小朋友个数n 下面n行 ai Output 求使所有人获得均等糖果的最小代价。 Sample Input 4 1 2 5 4 Sample Output 4 HINT 数据规模 30% n
C++贪心算法之均分纸牌
均分纸牌 题目描述 有 N 堆纸牌,编号分别为 1,2,…, N。每堆上有若干张,但纸牌总数必为 N 的倍数。可以在任一堆上取若于张纸牌,然后移动。移牌规则为:在编号为 1 堆上取的纸牌,只能移到编号为 2 的堆上;在编号为 N 的堆上取的纸牌,只能移到编号为 N-1 的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上。现在要求找出一种移动方法,用最少的移动次数使每堆上纸牌数都一样多。
Java集合框架的一个扑克牌小程序
* Game 类 * 功能:整个游戏:开始游戏 -> 初始牌 -> 洗牌 -> 发牌 -> 排序 -> 比较大小 -> 游戏结果 * 游戏说明: * 1.创建一副扑克牌,不考虑大小王 * 2.创建两名玩家,玩家至少要有ID、姓名、手牌等属性,手牌为扑克牌的集合 * 3.洗牌,将之前创建的扑克牌顺序打乱 * 4.发牌,将洗牌之后的扑克牌集合,从第一张开始,发给两名玩家,按照一人一张的方式,每人发两张 * 5.开始游戏,比大小,大小相同比花色 * * PockerCard 类 * 功能:扑克牌的核心类 包括创建角色、创建牌、显示牌、洗牌、比较牌、排序牌等 * 属性:List cards 整幅扑克牌的集合 、 People[] peoples 角色 * 方法: public PockerCard() //无参构造函数: 创建牌的集合、创建两个角色对象 * public void initializeCard() //创建整幅扑克牌 * public void showCard() //显示单支牌的花色和点数 * public void refreshCard() //洗牌 从第一支牌开始从所有牌中随机取一只与之交换 * public void addPeopleInfo() //添加玩家的基本信息 * public void dealCard() //发牌 从开始分别给A B发牌 每人两支 * public void showPeopleCard() //显示两个角色自己获得的牌 * public void sortCard() //将每个角色自己的牌按从小到大排序 * public void comparePeopleCard() //比较角色的牌 * * SingleCard类 实现Comparable接口 * 功能:产生单支牌 * 属性:ID、color、keyID数组、keyColor数组 * 方法:public SingleCard(){} //无参构造函数 * public SingleCard(String ID,String color) //有参构造函数 * @Override public int compareTo(SingleCard o) //比较当前牌与SingleCard o的牌的大小 * * People类 * 功能:产生一个角色 * 属性:ID、Name、和、存储牌的List集合。 * 方法: public People() //初始化存储牌的List集合; *
[编程题]纸牌博弈
题目描述:有一个整型数组A,代表数值不同的纸牌排成一条线。玩家a和玩家b依次拿走每张纸牌,规定玩家a先拿,玩家B后拿,但是每个玩家每次只能拿走最左或最右的纸牌,玩家a和玩家b都绝顶聪明,他们总会采用最优策略。请返回最后获胜者的分数。 给定纸牌序列A及序列的大小n,请返回最后分数较高者得分数(相同则返回任意一个分数)。保证A中的元素均小于等于1000。且A的大小小于等于300。 测试样例:[1,2
有关Java集合类的10大问题
原文地址:Top 10 questions about Java Collections
均分纸牌问题(贪心算法)
问题:N堆纸牌,纸牌总数是N的整数倍,求解给定情况下最少移动次数使得每堆纸牌数目相同。 /** * 均分卡片问题,贪心算法求解 * 如何移动最小步骤实现完成当前堆牌数等于均值,那就是从邻近堆借牌, * 在借牌时产生的负数问题,说明邻近堆牌数不足,需要从远处借调; * 把多于均值的理解为高处,把小于均值的理解为低处,在牌从高处走向低处时, * 如果有重复移动,如a,b,c相邻,b堆移动1
Java集合类相关面试题
ArrayList LinkedList Vector Set TreeSet Map HashMap HashTable面试中经常碰到的一些集合类
说难就难的贪心(一)——均分纸牌问题
类型 有N堆纸牌,编号分别为 1,2,…,N。每堆上有若干张,但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌,然后移动。 移牌规则为:在编号为1的堆上取的纸牌,只能移到编号为2的堆上;在编号为N的堆上取的纸牌,只能移到编号为N-1的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上。 现在要求找出一种移动方法,用最少的移动次数使每堆上纸