发展辅导委员的考验 时间限制:1000 ms 内存限制:65535 KB 总提交:4 (2 users) 正确提交:1 (1 users) 描述 发展辅导委员是3621大班的要职。为了选拔出最佳人选，辅导员想出了一个难题来考验竞选者的毅力。 辅导员给出了一个矩阵链< A1, A2, ...,An >，他要竞选者计算这n个矩阵的乘积！！ 聪明的你突然想到算法课上的最优矩阵连乘的算法。于是你决定用最优的矩阵连乘全括号方式，使得矩阵链乘积的乘法次数最少，用此方式计算矩阵链的乘积。 输入 多组输入，第一个正整数T表示组数。 每组第一行有一个正整数n，1≤n≤50表示矩阵个数。 第二行为p0,p1,…,pn共n+1个正整数，1≤pi≤50，pi-1×pi为矩阵Ai的大小 接下来为n个矩阵。 第i个矩阵有pi-1行，每行有pi个整数（在32位int范围内）。 输出 每组第一行输出矩阵链乘积乘法的最少次数， 接下来输出矩阵链的乘积(将该矩阵里每个元素对2008取余后输出)。 样例输入 2 2 2 3 4 2 3 1 1 2 3 3 3 1 1 3 3 2 3 3 2 2 3 3 2 4 4 4 19 93 72 46 32 45 33 99 48 89 3 30
26
37 49 71 73 94 56 41 81 78 13 2 30 72 34 3 79 24 1 94 2 94 18 99 81 53 52 81 29 样例输出 24 18 17 10 14 18 15 11 16 64 591 1604 830 822 820 42 1705 121 ? ? ? ? ? 问题 提交 状态 统计信息 记分板 发展辅导委员的考验 时间限制:1000 ms 内存限制:65535 KB 总提交:4 (2 users) 正确提交:1 (1 users) 描述 发展辅导委员是3621大班的要职。为了选拔出最佳人选，辅导员想出了一个难题来考验竞选者的毅力。 辅导员给出了一个矩阵链< A1, A2, ...,An >，他要竞选者计算这n个矩阵的乘积！！ 聪明的你突然想到算法课上的最优矩阵连乘的算法。于是你决定用最优的矩阵连乘全括号方式，使得矩阵链乘积的乘法次数最少，用此方式计算矩阵链的乘积。 输入 多组输入，第一个正整数T表示组数。 每组第一行有一个正整数n，1≤n≤50表示矩阵个数。 第二行为p0,p1,…,pn共n+1个正整数，1≤pi≤50，pi-1×pi为矩阵Ai的大小 27
接下来为n个矩阵。 第i个矩阵有pi-1行，每行有pi个整数（在32位int范围内）。 输出 每组第一行输出矩阵链乘积乘法的最少次数， 接下来输出矩阵链的乘积(将该矩阵里每个元素对2008取余后输出)。 样例输入 2 2 2 3 4 2 3 1 1 2 3 3 3 1 1 3 3 2 3 3 2 2 3 3 2 4 4 4 19 93 72 46 32 45 33 99 48 89 3 30 37 49 71 73 94 56 41 81 78 13 2 30 72 34 3 79 24 1 94 2 94 18 99 81 53 52 81 29 样例输出 24 18 17 10 14 18 15 11 16 64 591 1604 830 822 820 42 1705 121 28
数字三角形 时间限制:1000 ms 内存限制:65536 KB 总提交:68 (32 users) 正确提交:22 (22 users) 描述 7 3 8 8 1 0 2 7 7 4 5 5 2 6 5 如上所示出的一个数字三角形宝塔。数字三角形中的数字为不超过100的正整数。现规定从最顶层走到最底层，每一步可沿左斜线向下或右斜线向下走。假设三角形行数≤100，设计一个算法，找到从最顶层走到最底层的一条路径，使得沿着该路径所经过的数字的总和最大，输出最大值。 输入 第一行一个整数T，表示有T组测试数据。 对于每组测试数据：第一行是三角形的行数N。以后的N行分别是从最顶层到最底层的每一层中的数字。 输出 对于每组测试数据输出一行：最佳路径所对应的最大值。 样例输入 1 5 7 3 8 8 1 0 2 7 7 4 5 5 2 6 5 样例输出 30 29
石子取数 时间限制:1000 ms 内存限制:65535 KB 总提交:51 (16 users) 正确提交:4 (4 users) 描述 这是一个很古老的游戏，现在有n 堆石子排成一排，第 i 堆石子的数量为 ai, 两个人轮流取石子，每次只能从两边的石子中取走一堆且必需取走一堆。直到把n 堆石子都取完，取到较多石子的一方获胜。 Lqs 和 yuki 正在饶有趣味的玩着这个游戏： 对于一线ACM 队员来说，他们在玩游戏的时候自然都采用了最优策略，也就是说其实在n 堆石子的数量给定的时候，结果也已经确定了。。。 输入 第一行为一个整数T，表示有T组测试数据 对于每组测试数据，第一行一个整数n (n <= 100) ,即石子的堆数，接下来有n 个整数，第 i 个整数表示第 i 堆石子的数量。 输出 对于每组测试数据输出一行，两个用空格隔开的整数，依次为玩家一(先取的玩家)和玩家二（后取的玩家）所获得的石子数。 样例输入 2 4 1 2 3 4 4 1 3 4 2 样例输出 6 4 5 5 星际航班 30