设F[i,j]表示第K行第i个数到第j个数能得到的最大值。

那么F[i,j]表示的取数次数为第(m-j+i)次,倒数第(j-i)次

那么有：

[b]F[i,i]:= num[k,i] * 2^m [/b]

即F[i,i]表示第i个数为最后一个取时能得到的最大值

而对于整个F[i,j]来说，第i个数,第j个数皆可能为倒数第(j-i)次取数

[b]①F[i,j] = F[i+1,j] + num[k,i] * 2^(m-j+i) [/b] 或者

[b]②F[i,j] = F[i,j-1] + num[k,j] * 2^(m-j+i) [/b] 在这之间取最大值即可咯

故[b][color=yellow]F[i,j] = max(①,②); [/color][/b]

这样我们计算的顺序应该是

(1,1),(2,2)...(m,m),(1,2),(2,3)...(m,m-1),(1,3)....

可以看出是由表内计算到表外的，用一些特殊的枚举技巧

For k=1 → n

For i=1 → m //i 枚举长度

For j=1 → m //j 枚举起点

此时 [b]①F[j+1,j+i-1]+num[k,j]*2^(m-i+1) [/b]

[b]②F[j,j+i-2]+num[k,j+i-1]*2^(m-i+1) [/b]

[b][color=yellow]F[j,j+i-1] = max(①,②); [/color][/b]

[hr] 正确性应该没问题→ →，高精度还是分段就交给你们吧。