题目描述 给定一个由 n 个正整数组成的数列，对数列进行一次操作：去除其中两项 a、b，然后添加一项 a×b+1。每操作一次数列减少一项，经 n−1 次操作后该数列只剩一个数。试求在 n-1 次操作后最后得数的最大值。 输入描述 多组输入，每组两行，第一行输入正整数 n，第二行输入 n 个正整数 n<20 输出描述 对每组输入，输出最后剩下的一个 样例输入 Copy to Clipboard 6 8 9 3 6 5 4 样例输出 Copy to Clipboard 29493

解题思路：

首先，我们可以想到对于给定的数列，每次取出两个数 a、b，将它们从数列中删除，然后将 a * b + 1 加入数列中。显然，每次操作后，数列中的元素数目会减少 1。因此，经过 n-1 次操作后，数列中只剩下一个元素。考虑利用这个特点，通过模拟整个操作过程，求出最后剩下的元素的最大值。

具体而言，我们可以使用回溯法来枚举每一次操作。具体地，从数列中选择两个数 a、b，将它们从数列中删除，然后计算 a * b + 1 并加入数列中。接着，我们对新的数列调用递归函数，继续执行下一次操作。当数列中只剩下一个元素时，更新最大值并返回。

时间复杂度：O(2^n)

参考代码：

相关问题

给定一个由 n 个正整数组成的数列，对数列进行一次操作：去除其中两项 a、b，然后添加一项 a×b+1。每操作一次数列减少一项，经 n−1 次操作后该数列只剩一个数。试求在 n-1 次操作后最后得数的最大值。

这道题可以使用数学归纳法证明，最后得数的最大值为 (a1×a2×...×an+1) - 1。

当 n=2 时，显然最后得数的最大值为 a1×a2-1。

假设当 n=k 时结论成立，即经过 k-1 次操作后最后得数的最大值为 (a1×a2×...×ak+1) - 1。

考虑当 n=k+1 时，我们可以先对前 k 个数进行 k-1 次操作，得到最终的数为 (a1×a2×...×ak+1) - 1。然后再将第 k+1 个数与该数进行一次操作，得到的新数为 (a1×a2×...×ak×ak+1+1) - 1。

因此，经过 k 次操作后最后得数的最大值为 (a1×a2×...×ak×ak+1+1) - 1，结论成立。

综上所述，经过 n-1 次操作后最后得数的最大值为 (a1×a2×...×an+1) - 1。

C语言给定一个由 n 个正整数组成的数列，对数列进行一次操作：去除其中两项 a、b，然后添加一项 a×b+1。每操作一次数列减少一项，经 n−1 次操作后该数列只剩一个数。试求在 n-1 次操作后最后得数的最大值。

这道题可以使用贪心算法来解决。

我们观察题目中的操作，可以发现每一次操作都会把数列中的两个数合并成一个数，同时把数列的长度减少 1。因此，我们可以考虑把数列中的最大值和次大值合并，这样可以保证合并后得到的新数是最大的。

具体地，我们可以维护一个最大堆，每次从最大堆中取出最大的两个数，合并后再将结果加入最大堆中。重复执行这个过程，直到堆中只剩下一个数，这个数就是最终得数的最大值。

代码实现如下：