10 000 001 011 010 110 111 101 100 21
快乐的YK 时间限制:1000 ms 内存限制:65536 KB 总提交:73 (35 users) 正确提交:32 (32 users) 描述 没有买到奥运会的门票让Yk伤心不已，为了使自己开心起来，他去找周围的人聊天，每找一个人聊天，他就会耗费一定的体力，但他会得到一定量的快乐。Yk试图使自己尽可能的高兴，但一旦体力耗尽了(为零或为负)，他也就挂了，就一点快乐都没有了。现在Yk初始有100点体力，他最多可以获得多少快乐？ 输入 数据分多组，对于每组数据：第一行为n，表示有YK的n(0< n < 21)个朋友。第二行表示和每个人聊天要耗费的体力值，第三行表示每个人所能提供的快乐值。输入以一个0结束。 输出 对于每组输出，输出一个值，YK可以获得的最大的快乐值。 样例输入 3 1 21 79 20 30 25 4 100 100 100 100 1 2 3 4 0 样例输出 50 0 装配线调度2 时间限制:1000 ms 内存限制:1000 KB 总提交:39 (19 users) 正确提交:3 (3 users) 22
描述 某汽车工厂有2个装配线，每个装配线有n 个装配站（按顺序编号1～n ），两个装配线对应的装配站执行相同的功能，但所用的时间可能不同。经过第i条流水线（i=1，2）的第j 个装配站所花的时间为Aij。从第i条流水线的第j 个装配站移到第j+1个装配站的时间可以忽略，而移到另外一个流水线的下一个装配站则需要一定的时间Tij。 汽车进入流水线不需要花时间，出流水线时需要花时间Tin。 汽车的装配需要按顺序经过所有装配站。 现在已知装配时间Aij 和转移时间Tij，要求输出装配一辆汽车所需要的最短时间。 注意：根据练习15.1-4 压缩存储空间的指示精神，本题做了较为严格的内存限制(其实还可以更严)。。。 输入 第一行为一个整数T，表示有T 组测试数据。 对于每组测试数据的第一行一个整数n （n <= 100,000）,表示有n 个装配站。接下来的n 行按顺序给出了n 个装配站信息，其中第 j 行有4个整数A1j ,A2j ,T1j ,T2j。 输出 对于每组测试数据，输出两行：第一行一个整数即最短时间。第二行从n 到1 倒序输出经过的装配站所在的流水线的编号。（数据保证最优方案只有一种） 样例输入 1 6 7 8 2 2 9 5 3 1 3 6 1 2 4 4 3 2 8 5 4 1 4 7 3 2 样例输出35 1 2 2 1 2 2
23
奇怪的梦 时间限制:1000 ms 内存限制:65536 KB 总提交:31 (11 users) 正确提交:2 (2 users) 描述 上完算法课回来的路上，你仍然为DP的优美而赞叹不已。 正所谓日有所思，夜有所梦，午觉也不例外。因为研究DP太过投入，睡午觉的时候你做了一个很奇怪的梦。 梦里你回到了19世纪。那时的人们还没有计算机的概念。而很不幸的，在时空旅行中你带上了你的笔记本。所以很自然的，你成为了那个年代最伟大的科学家之一。 这天，你和一群科学家同伴聚会。会上讨论了矩阵链乘法问题。当时还没有很好的解决方法。而你想到了刚刚算法课上讲到的动态规划方法（为什么是刚刚？？应该是很久以后......）。 PS：有关矩阵链乘法问题参考算法导论第十五章第2节。 输入 第一行只有一个整数n，表示矩阵链的数目。 每条矩阵链描述如下： 第一行是一个整数m(0 < m <= 100)。表示一共有m个矩阵 接下来的m行每行一对整数Pi,Qi(0< Pi,Qi <=100)。表示矩阵Ai的维数。 输入数据保证矩阵相容。 输出 每条矩阵链输出两行。 第一行一个整数，表示最小的标量乘法次数。 第二行用加括号的方式描述此方法 当最优解不唯一时，按先左后右的顺序相乘。 例如有3个矩阵A1,A2,A3。当((A1A2)A3)和(A1(A2A3))相等时，输出((A1A2)A3)。 样例输入 1 6 30 35
24
35 15 15 5 5 10 10 20 20 25 样例输出 15125 ((A1(A2A3))((A4A5)A6)) 25