题目描述： Py要把一根长木棒分割成n段,首先把长木棒分割成两段,然后每次从分割出来木棒中取出一根来分割成两段,最后得到n段.把一根长为m的木棒分成两段的费用为m.Py希望分割的费用尽可能少,请你找到这个最小费用.. 给你一个正整数n(1<=n<=2000，表示分割成多少段)和一个长度为n的正整数列表L(L中的元素表示分割成的每一段的长度),长木棒的长度等于这n个数的和,分割中不会有损失. 请你输出一个正整数，表示分割所需的最少总费用。 如： n = 5 L = [1,2,3,4,5] 则输出： 33
提示：原始木棒的长度为15,首先分割为6和9两段(费用15),然后把长为9的分成4和5两段(费用9),接着把长为6木棒分为3和3两段(费用6),最后把长为3的一段分为1和2两段(费用3). 总费用为:15 + 9 + 6 + 3 = 33
示例： 输入： n = 1886 L = [139, 100, 120, 164, 131, 197, 34, 63, 39, 104, 161, 48, 6, 79, 173, 76, 185, 179, 194, 184, 113, 169, 89, 82, 25, 172, 136, 97, 139, 134, 56, 103, 192, 166, 87, 138, 39, 124, 133, 112, 53, 54, 5, 4, 63, 148, 42, 81, 171, 193, 170, 126, 150, 185, 184, 73, 49, 53, 200, 10, 115, 65, 153, 52, 163, 191, 32, 99, 54, 168, 22, 34, 32, 159, 3, 37, 90, 114, 175, 191, 160, 71, 154, 192, 125, 153, 199, 150, 31, 21, 35, 74, 20, 161, 191, 97, 56, 2, 3, 11, 85, 126, 86, 122, 91, 41, 86, 13, 81, 180, 118, 22, 155, 39, 81, 143, 19, 144, 113, 57, 149, 56, 90, 124, 166, 18, 82, 189, 72, 175, 34, 53, 95, 153, 164, 91, 109, 112, 161, 165, 80, 114, 67, 17, 59, 117, 101, 156, 88, 68, 144, 107, 91, 200, 27, 132, 131, 61, 82, 92, 125, 113, 156, 35, 141, 4, 27, 198, 17, 153, 145, 103, 189, 116, 155, 176, 51, 91, 131, 112, 153, 93, 126, 65, 188, 73, 146, 25, 19, 179, 40, 136, 145, 67, 72, 91, 78, 151, 50, 1, 124, 99, 8, 15, 117, 107, 55, 54, 89, 88, 198, 80, 108, 5, 56, 94, 106, 94, 178, 10, 93, 36, 189, 109, 35, 102, 187, 1, 187, 106, 156, 173, 62, 126, 175, 73, 176, 52, 49, 85, 46, 20, 185, 58, 10, 21, 10, 90, 130, 138, 27, 57, 165, 185, 68, 22, 101, 69, 59, 127, 80, 18, 82, 148, 123, 185, 200, 186, 160, 163, 135, 198, 86, 174, 146, 158, 161, 101, 150, 63, 75, 194, 64, 165, 75, 132, 174, 1, 183, 52, 126, 77, 156, 76, 108, 108, 140, 53, 196, 157, 133, 135, 51, 183, 22, 128, 52, 62, 86, 151, 110, 163, 49, 113, 155, 134, 153, 164, 95, 1, 137, 52, 137, 40, 174, 159, 55, 32, 198, 76, 80, 139, 18, 68, 164, 162, 127, 30, 14, 199, 118, 110, 177, 28, 111, 188, 99, 68, 124, 21, 4, 127, 68, 171, 50, 60, 84, 123, 162, 23, 86, 135, 194, 37, 140, 133, 190, 148, 149, 185, 198, 18, 35, 1, 97, 111, 38, 109, 47, 78, 82, 119, 95, 159, 34, 101, 151, 67, 173, 150, 96, 187, 154, 9, 19, 101, 55, 52, 10, 5, 57, 75, 110, 173, 24, 121, 179, 95, 84, 162, 14, 90, 52, 136, 104, 94, 2, 121, 125, 171, 196, 145, 144, 37, 152, 32, 29, 4, 141, 67, 186, 27, 199, 75, 150, 9, 158, 86, 60, 11, 191, 119, 200, 69, 36, 162, 68, 60, 155, 94, 94, 115, 189, 97, 58, 68, 51, 135, 108, 147, 166, 17, 122, 133, 169, 171, 174, 148, 9, 164, 43, 134, 37, 12, 32, 114, 154, 57, 37, 104, 82, 88, 89, 153, 31, 32, 182, 198, 131, 4, 82, 166, 151, 198, 76, 130, 175, 22, 100, 162, 43, 23, 118, 130, 77, 59, 93, 1, 90, 2, 172, 186, 190, 41, 181, 162, 63, 28, 32, 146, 139, 170, 94, 135, 33, 194, 110, 171, 166, 62, 21, 49, 172, 170, 185, 193, 160, 126, 124, 196, 85, 138, 46, 49, 189, 128, 7, 182, 67, 67, 199, 143, 39, 7, 68, 74, 124, 161, 15, 30, 198, 20, 16, 129, 195, 63, 45, 127, 142, 8, 69, 38, 8, 149, 136, 195, 124, 160, 15, 171, 107, 85, 171, 92, 112, 47, 98, 21, 104, 37, 3, 111, 22, 28, 7, 104, 48, 32, 69, 68, 187, 84, 182, 165, 136, 59, 64, 123, 122, 107, 67, 76, 1, 71, 134, 48, 146, 52, 199, 38, 177, 158, 158, 62, 70, 186, 183, 41, 176, 159, 119, 152, 128, 98, 139, 22, 82, 182, 83, 131, 169, 149, 72, 188, 25, 126, 68, 67, 63, 101, 97, 115, 158, 158, 10, 168, 65, 43, 14, 141, 89, 31, 102, 105, 120, 176, 147, 91, 185, 89, 31, 154, 123, 113, 112, 179, 83, 64, 59, 28, 65, 186, 81, 26, 18, 73, 29, 36, 7, 65, 45, 105, 102, 80, 160, 102, 126, 36, 158, 65, 149, 105, 33, 9, 46, 68, 17, 152, 78, 107, 30, 12, 80, 139, 102, 188, 190, 83, 135, 133, 77, 87, 153, 53, 37, 133, 188, 34, 103, 10, 144, 87, 50, 19, 199, 118, 118, 105, 89, 43, 122, 6, 96, 184, 113, 109, 104, 181, 158, 178, 94, 101, 136, 189, 148, 66, 119, 186, 75, 156, 11, 47, 152, 154, 112, 3, 95, 114, 191, 71, 69, 90, 114, 174, 165, 30, 64, 183, 72, 42, 173, 141, 13, 48, 83, 184, 177, 138, 107, 25, 29, 57, 47, 183, 68, 52, 55, 91, 33, 41, 157, 126, 74, 111, 52, 83, 23, 91, 99, 80, 164, 173, 30, 139, 155, 148, 135, 189, 89, 122, 187, 66, 111, 117, 178, 6, 135, 128, 3, 131, 5, 37, 58, 171, 120, 31, 72, 29, 84, 114, 172, 191, 15, 51, 53, 157, 52, 190, 100, 58, 83, 7, 45, 30, 57, 192, 11, 1, 56, 120, 144, 104, 144, 144, 110, 187, 113, 148, 98, 26, 78, 132, 134, 164, 138, 173, 92, 91, 96, 43, 82, 76, 139, 155, 120, 73, 27, 2, 42, 77, 74, 42, 127, 8, 144, 76, 24, 55, 125, 86, 141, 180, 76, 12, 138, 8, 30, 65, 147, 194, 85, 167, 126, 15, 84, 59, 179, 59, 85, 3, 26, 142, 38, 58, 45, 117, 112, 133, 162, 93, 83, 196, 22, 1, 82, 131, 158, 76, 80, 42, 123, 21, 141, 133, 149, 181, 112, 97, 173, 193, 180, 141, 193, 24, 34, 171, 183, 3, 88, 114, 104, 138, 66, 129, 63, 150, 85, 123, 172, 146, 3, 50, 77, 168, 168, 104, 93, 132, 104, 112, 47, 28, 120, 108, 62, 107, 134, 194, 161, 48, 85, 164, 23, 92, 78, 8, 73, 91, 113, 68, 29, 174, 72, 51, 168, 95, 81, 22, 31, 81, 102, 193, 196, 32, 97, 86, 130, 42, 184, 58, 177, 147, 26, 105, 74, 166, 65, 15, 138, 35, 140, 115, 48, 140, 178, 30, 105, 113, 156, 138, 14, 178, 58, 126, 175, 31, 54, 190, 113, 55, 3, 85, 12, 199, 72, 65, 161, 20, 142, 74, 114, 32, 62, 43, 98, 101, 146, 200, 129, 113, 197, 106, 170, 103, 185, 70, 131, 193, 131, 28, 125, 18, 101, 49, 120, 57, 22, 33, 3, 66, 129, 32, 99, 18, 6, 169, 173, 119, 170, 168, 191, 34, 196, 177, 34, 90, 114, 5, 16, 195, 137, 12, 87, 84, 140, 117, 46, 175, 23, 31, 166, 38, 162, 93, 165, 95, 101, 75, 124, 85, 180, 77, 158, 56, 25, 38, 191, 134, 70, 152, 176, 29, 63, 35, 138, 140, 195, 72, 184, 165, 126, 53, 85, 173, 81, 108, 28, 120, 48, 106, 90, 5, 89, 45, 162, 28, 83, 137, 169, 8, 70, 137, 81, 68, 147, 27, 43, 74, 191, 137, 178, 146, 122, 45, 45, 130, 25, 22, 32, 188, 7, 181, 80, 13, 194, 71, 56, 66, 27, 199, 148, 101, 118, 55, 101, 179, 15, 112, 41, 38, 119, 174, 124, 32, 147, 20, 126, 188, 143, 169, 195, 39, 112, 134, 112, 194, 10, 5, 35, 152, 66, 142, 166, 33, 189, 119, 166, 155, 134, 148, 95, 193, 99, 100, 110, 176, 61, 159, 23, 74, 84, 196, 77, 8, 79, 15, 167, 40, 170, 96, 187, 116, 57, 33, 116, 141, 125, 42, 26, 86, 195, 10, 3, 159, 163, 138, 42, 104, 170, 31, 29, 45, 162, 98, 94, 86, 164, 54, 162, 154, 136, 130, 156, 70, 181, 69, 55, 110, 77, 86, 131, 146, 97, 167, 20, 107, 131, 71, 105, 118, 103, 41, 43, 71, 50, 117, 124, 164, 143, 33, 53, 92, 56, 16, 76, 38, 165, 138, 33, 48, 122, 151, 128, 123, 120, 82, 122, 82, 51, 75, 169, 113, 96, 129, 16, 181, 85, 91, 127, 183, 90, 69, 79, 164, 124, 76, 178, 127, 43, 150, 90, 30, 63, 109, 148, 177, 192, 49, 42, 184, 134, 196, 172, 138, 159, 169, 98, 32, 112, 114, 165, 198, 162, 155, 109, 127, 46, 95, 21, 101, 194, 143, 98, 90, 164, 19, 197, 120, 153, 170, 101, 15, 149, 152, 115, 74, 15, 118, 116, 168, 111, 46, 137, 94, 195, 37, 152, 70, 54, 95, 185, 21, 15, 34, 77, 179, 71, 146, 103, 199, 41, 70, 197, 80, 170, 158, 159, 187, 74, 152, 11, 62, 141, 69, 96, 169, 90, 127, 53, 150, 173, 185, 22, 31, 17, 170, 103, 108, 67, 188, 155, 99, 189, 172, 193, 87, 178, 135, 103, 7, 4, 38, 77, 94, 44, 136, 152, 133, 94, 119, 118, 165, 177, 159, 120, 110, 27, 9, 57, 75, 63, 78, 6, 23, 31, 135, 24, 134, 163, 99, 148, 186, 88, 81, 182, 150, 117, 102, 123, 42, 37, 133, 53, 102, 41, 165, 43, 116, 148, 78, 138, 1, 2, 78, 182, 185, 60, 177, 87, 185, 175, 194, 160, 110, 179, 5, 1, 163, 156, 117, 190, 75, 1, 48, 144, 171, 66, 162, 25, 162, 61, 55, 81, 34, 164, 163, 130, 23, 2, 153, 39, 109, 173, 49, 192, 76, 155, 190, 45, 146, 178, 111, 27, 171, 197, 71, 184, 112, 85, 109, 82, 139, 148, 116, 112, 71, 93, 117, 139, 173, 105, 15, 35, 65, 161, 95, 20, 38, 167, 72, 11, 185, 200, 109, 44, 157, 82, 136, 36, 150, 196, 199, 130, 199, 7, 91, 189, 20, 134, 68, 192, 57, 103, 2, 42, 100, 174, 122, 114, 66, 114, 31, 92, 5, 9, 199, 190, 117, 117, 102, 30, 70, 135, 117, 97, 99, 70, 124, 112, 102, 152, 131, 52, 137, 29, 78, 9, 33, 86, 197, 108, 159, 179, 50, 29, 7, 87, 120, 24, 160, 22, 179, 183, 181, 90, 162, 192, 119, 42, 94, 188, 170, 193, 72, 160, 41, 16, 57, 78, 200, 182, 177, 178, 41, 54, 66, 113, 1, 26, 17, 148, 77, 122, 104, 38, 183, 141, 24, 29, 199, 119, 121, 63, 157, 192, 158, 170, 37, 182, 53, 115, 106, 126, 110, 87, 78, 90, 100, 116, 75, 197, 54, 31, 103, 33, 43, 15, 117, 141, 87, 165, 57, 118, 12, 195, 23, 171, 31, 76, 3, 200, 145, 54, 96, 121, 5, 67, 150, 188, 131, 78, 82, 60, 21, 159, 161, 61, 71, 141, 62, 149, 164, 132, 116, 77, 97, 42, 126, 52, 24, 15, 55, 69, 48, 140, 48, 121, 61, 121, 13, 16, 181, 118, 155, 161, 158, 46, 159, 140, 2, 154, 9, 166, 79, 173, 123, 76, 113, 33, 49, 43, 109, 28, 178, 45, 166, 106, 32, 177, 108, 118, 159, 115, 82, 14, 39, 169, 139, 188, 39, 102, 154, 18, 89, 50, 53, 194, 47, 125, 26, 53, 50, 73, 60, 187, 60, 41, 29, 42, 186, 50, 171, 93, 157, 136, 99, 15, 116, 167, 76, 74, 174, 161, 56, 8, 107, 189, 123, 16, 65, 20, 196, 158, 93, 69, 181, 64, 15, 157, 77, 110, 199, 153, 117, 123, 186] 输出： 2047558
分析: 稍等片刻。。。。
代码:
1
精彩马上继续。。。。。