请编程高手们帮忙看看一道题，中学生级别的，持分等待。。。

rainwater

最好是用C#或C++，刚开始学习，很多地方弄不明白，请高手们帮帮忙

Input File: ticketin.txt
Output File: ticketout.txt
Time Limit: 1 second

假设有人去一个城市旅游，有两种车票，3天票$4，5天票$7，他要出门的天数是分别是第1, 2, 4, 6, 8, 13 和 16天，这样的话，他应该买两个5天票一个3天票，总共最小花费是18元。

题目要求是
input file:
4 3.......票价 天数
7 5......票价 天数
7.........出门的天数
1.........第几天
2
4
6
8
13
16

output file
要求算出最小花费

HappyRain

给你个思路，每一次买票 都从出门 那一天开始，往后 累加 到后面出门那天 的 总天数，买能够覆盖天数最便宜的票

请见下面的例子。

例如：
   1） 从出门第1天开始， 1， 2， 4  共 4 天，所以买 5天票 $7。 （ 如果再算上下一次出门那天，1，2，4，6 总天数为6天，没有这么长的票。所以第一次买 5天票 $7。）

   2） 第6天又出门了，同理，往后看，: 6, 8 共3天，（如果再算上下一次出门那天 6，8，13 总天数为8天，没有这么长的票），所以这次买3天的票$4
   
   3)  最后第13天又出门了， 13，16共4天，后面不出门了，所以这次就买能够覆盖天数最便宜的票，,只有5天$7

所以，总共买了两个5天票，一个3天票，最小花费是18元。

注意：不同的票价参数，需要测试算法的正确性。

rainwater

HappyRain 发表于 2014-7-9 15:48
给你个思路，每一次买票 都从出门 那一天开始，往后 累加 到后面出门那天 的 总天数，买能够覆盖天数最便宜 ...

多谢回复！

这个方法我想过了，但是有个问题，万一是第1，5，6，7，8，9天出门呢?
照这个算法，第一次买够5天，1，5。剩下的还得买5天票。而实际上第一次买3天票，接下来买5天票就够了。

这种情况怎么解决呢?

nineyes

如果数字不大只有100天内就把所有可能列出来让电脑自己算
如果数字很大就分段

我觉得最好的建议是买月票

stevenbian

遍历二叉树中学生就学了？

rainwater

nineyes 发表于 2014-7-9 16:06
如果数字不大只有100天内就把所有可能列出来让电脑自己算
如果数字很大就分段

多谢回复！能再详细些吗?如何分段?每个可能都做的话不会time out吗?

题目要求是：
旅行天数是0 ≤ D ≤ 10,000
票价是$1到$1000的范围
票的有效天数是1到100天之内

rainwater

stevenbian 发表于 2014-7-9 16:36
遍历二叉树中学生就学了？

听上去很高深的样子，放狗搜了一下，还是不大明白，能详细解释一下吗?谢谢！

rainwater

stevenbian 发表于 2014-7-9 16:36
遍历二叉树中学生就学了？

中学生没学过，所以不懂呀

stevenbian

就是搞一个二叉树左节点是3天右节点是5点，用你的天数遍历一遍子节点，然后找个价格最小的就行了。

rainwater

stevenbian 发表于 2014-7-9 17:00
就是搞一个二叉树左节点是3天右节点是5点，用你的天数遍历一遍子节点，然后找个价格最小的就行了。 ...

多谢了！在youtube上找到不少视频教这个的，好好学学，但愿能弄懂。

很明显

笑而不语

kane321

很明显 发表于 2014-7-11 21:52
笑而不语

咋 这么快就编辑了啊?

lena07

这不是最简单的线性规划问题吗

rainwater

很明显 发表于 2014-7-11 21:52
笑而不语

别不语呀，帮忙看看，给个思路也行

rainwater

lena07 发表于 2014-7-12 11:06
这不是最简单的线性规划问题吗

能详细解释一下吗?谢谢！

joerkky

rainwater 发表于 2014-7-12 12:46
能详细解释一下吗?谢谢！

http://wiki.mbalib.com/wiki/%E6%95%B4%E6%95%B0%E8%A7%84%E5%88%92

很明显

叹服澳洲IT界

鱼羊鲜

厉害

toro

看不懂 原 po 所要表達的方式@@