高精度的题目为什么不用python？（说实在的，这是我第一次用python做dp）

n,m=[int(i) for i in raw_input().split()]
ans=0
while n>0:
    n-=1
    f=[[0]*(m-i) for i in range(m)] #从j往后选i个数的最优解
    f[0]=[int(i) for i in raw_input().split()]
    for i in range(1,m):
        for j in range(m-i):
            if i==1:
                f[i][j]=2*max(f[0][j]*2+f[0][j+1],f[0][j+1]*2+f[0][j])
            else:
                f[i][j]=f[i-1][j+1]+f[0][j]
                f[i][j]=2*max(f[i][j],f[i-1][j]+f[0][i+j])
    ans+=f[m-1][0]
print(ans)

依题意得，行与行之间毫无关联，因此各行之间相互独立，完全可以一行一行地处理。每一行都选出一个最大值，加起来就是答案了。对于第 i 行，每次都只能从两边取，所以一个状态只可能由两个状态转移而来：左边或右边。令**f[l][r]代表从左起边取了l个，右边起取了r个数的最高分值。**用目前是第几次取来划分阶段。
方程很好想： f[l][r] = Max{ f[l-1][r] + matrix[i][l-1] · 2^j, f[l][r-1] + matrix[i][m-r] · 2^j }
其中 matrix 存储矩阵，i 表示目前正在处理第几行，所以 matrix[ i ][ 0 .. m-1] 存储的是该行的数字。j 表示目前是第几次取。写成代码如下：

for(i=0; i<row; i++){
memset(f, 0, sizeof(f));
for(j=1; j<=column; j++){ //columns taken
for(l=0; l<=j; l++){ //columns taken from left side
r = j-l; //columns taken from right side
if(l > 0)
f[l][r] = f[l-1][r] + matrix[i][l-1]*pow(2, j);
if(r > 0)
f[l][r] = MAX(f[l][r], f[l][r-1] + matrix[i][column-r]*pow(2, j));
}
}
j = 0;
for(l=0; l<=column; l++)
j = MAX(j, f[l][column-l]);
sum += j;
}

由于数据范围很大，所以需要高精度，还要预处理一下 2 的幂。写了一百多行就不贴上来了。本以为常数很大，但加起来不到 600ms 就 AC 了。注意第一组测试数据，貌似答案是0，结果我忘记考虑这一点，没有输出，还WA了一次。

大整数模板我就不贴出来了，这里给一个之前没有加大整数的题解便于理解，该题解60分。
首先，对整个矩阵取数，由于行与行之间取数的独立性。我们可以理解为对矩阵的每一行都取一遍。
接下来看一行怎么取，记dp(i,j)为i到j之间的数字都没取过，从两端向中间dp。初始化dp(0,m-1)=0.

dp[k][r]=max(dp[k-1][r]+ma[i][k-1]*base,dp[k][r+1]+ma[i][r+1]*base);

题解：

#include <iostream>
#include <cstring>
#define ULL unsigned long long

using namespace std;

int n,m;
int ma[80][80];
ULL dp[80][80];

int main()
{
    cin>>n>>m;
    int i,j,k,r;
    ULL ans=0,base,hax;
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            cin>>ma[i][j];
        }
    }
    for(i=0;i<n;i++)
    {
        memset(dp,0,sizeof(dp));
        base=2;
        hax=0;
        for(j=1;j<m;j++,base*=2)
        {
            for(k=0;k<=j;k++)
            {
                r=m-1-j+k;
                if(k==0)
                {
                    dp[k][r]=dp[k][r+1]+ma[i][r+1]*base;
                }
                else if(k==j)
                {
                    dp[k][r]=dp[k-1][r]+ma[i][k-1]*base;
                }
                else
                {
                    dp[k][r]=max(dp[k-1][r]+ma[i][k-1]*base,dp[k][r+1]+ma[i][r+1]*base);
                }
            }
        }
        for(j=0;j<m;j++)
        {
            hax=max(hax,dp[j][j]+ma[i][j]*base);
        }
        ans+=hax;
    }
    cout<<ans<<endl;
    return 0;
}

编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 3480 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 3484 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 3480 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 3484 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 3484 KiB, score = 10
测试数据 #5: Accepted, time = 46 ms, mem = 3480 KiB, score = 10
测试数据 #6: Accepted, time = 93 ms, mem = 3484 KiB, score = 10
测试数据 #7: Accepted, time = 296 ms, mem = 3484 KiB, score = 10
测试数据 #8: Accepted, time = 375 ms, mem = 3484 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 3480 KiB, score = 10
Accepted, time = 870 ms, mem = 3484 KiB, score = 100
思想下面有大犇给了，感觉自己代码*好长、好慢*啊~~

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
inline int read() {
    int t = 1,x = 0;
    char ch = getchar();
    while ( ch < '0' || ch > '9' ) {
        if ( ch == '-' ) t = -1;
        ch = getchar();
    }
    while ( ch >= '0' && ch <= '9' ) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return t * x;
}
struct node {
    int len,s[111];
    node() {len=1;memset(s,0,sizeof s);}
    node operator=(const char* num) {
        len = strlen(num);
        for (int i=0;i<len;i++) s[i] = num[len-i-1]-'0';
        return *this;
    }
    node operator=(const int num) {
        char a[101];
        sprintf(a,"%d",num);
        *this = a;
        return *this;
    }
    node(int num) {*this = num;};
    node operator+(const node & a) {
        node c;
        c.len = max(a.len,len)+1;
        for (int i=0,x=0;i<c.len;i++) {
            c.s[i] = s[i] + a.s[i] + x;
            x = c.s[i]/10;
            c.s[i] = c.s[i]%10;
        }
        while ( c.s[c.len-1] == 0 && c.len > 1 ) --c.len;
        return c;
    }
    node operator+=(const node & a) {
        *this = *this + a;
        return *this;
    }
    node operator*(const node & x) {
        node c;
        c.len = len + x.len;
        for (int i=0;i<len;i++) {
            for (int j=0;j<x.len;j++) {
                c.s[i+j] += s[i]*x.s[j];
                c.s[i+j+1] += c.s[i+j]/10;
                c.s[i+j]%=10;
            }
        }
        while (c.s[c.len-1] == 0 && c.len > 1) --c.len;
        return c;
    }
    bool operator < (const node & x) const {
        if ( len != x.len) return len<x.len;
        for (int i=len-1;i>=0;i--) {
            if ( s[i] != x.s[i] ) return s[i]<x.s[i];
        }
        return 0;
    }
};
node Max(node a,node b) {
    if ( a < b ) return b;
    else return a;
}
node che(int j) {
    node x = (int)1,y = 2;
    for (int i=1;i<=j;i++)
        x = x * y;
    return x;
}
void print(node a) {
    for (int i=a.len-1;i>=0;i--)
        cout<<a.s[i];
    cout<<endl;
}
node dp[81][81],ans;
int n,m,map[81][81];
int main() {
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    n = read(); m = read();
    for (int i=1;i<=n;i++) 
        for (int j=1;j<=m;j++)
            map[i][j] = read();
    for (int i=1;i<=n;i++) {
        node maxx;
        dp[0][0] = 0;
        dp[0][1] = (map[i][m] * 2);
        dp[1][0] = (map[i][1] * 2);
        for (int j=1;j<=m;j++) {
            node p = che(j);
            maxx = (int)0;
            for (int k=0;k<=j;k++) {
                node a = map[i][k],b = map[i][m-j+k+1];
                a = a * p;
                b = b * p;
                if ( k > 0 ) a = a + dp[k-1][j-k];
                if ( k < j ) b = b + dp[k][j-k-1];
                dp[k][j-k] = Max(a,b);
                if ( j == m ) maxx = Max(dp[k][j-k],maxx);
            }
        }
        ans += maxx;
    }   
    print(ans);
    return 0;
}

高精度直接python 自带高精度
然后直接dfs+记忆化搜素

递归选择取左边还是取右边

n,m=map(int,input().split())
ans=0
multipliers=[1 for _ in range(m)]
for i in range(m):
    multipliers[i]=multipliers[i-1]*2
for hang in range(n):
    nums=list(map(int,input().split()))
    dp=[[-1]*m for _ in range(m)]
    def dfs(i, j, k):
        if k == m:
            return 0
        if dp[k][i] != -1: return dp[k][i]
        dp[k][i] = max(nums[i] * multipliers[k] + dfs(i + 1, j, k + 1), nums[j] * multipliers[k] + dfs(i, j - 1, k + 1))
        return dp[k][i]
    ans+=dfs(0,m-1, 0)
print(ans)

如果使用GCC内置变量__uint128_t也是可以满足要求的，不用再写高精度类了

话说JAVA的BigInteger和Python真的是让人羡慕。

前面已经有个题解说得很好了。
我就贴个代码吧，主要还是考高精度，从2^80就可以看出long是存不下的。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
struct BIGINT {
    int len, num[35];   
    void CLEAR () {
        len=1;
        memset(num, 0, sizeof(num));    
    }
    void PRINT () {
        //printf("%d\n", len);
        for(int i=len; i>=1; i--) printf("%d", num[i]);     
    }
    BIGINT () {
        CLEAR();
    }
    BIGINT (int x) {
        CLEAR();    
        while(x) {
            num[len]=x%10;
            x/=10;
            len++;  
        }
        len--;
    }
    BIGINT operator + (BIGINT x) {
        BIGINT a;
        int maxlen=max(len, x.len);
        for(int i=1; i<=maxlen;i++) a.num[i]=num[i]+x.num[i];
        while(a.num[a.len]>=10||a.len<maxlen) {
            a.num[a.len+1]+=a.num[a.len]/10;
            a.num[a.len++]%=10;
        }    
        return a;
    }
    BIGINT operator * (BIGINT x) {
        BIGINT a;
        int maxlen=len+x.len-1;
        for(int i=1; i<=len; i++) 
            for(int j=1; j<=x.len; j++)
                a.num[i+j-1]+=num[i]*x.num[j];
        while(a.num[a.len]>=10||a.len<maxlen) {
            a.num[a.len+1]+=a.num[a.len]/10;
            a.num[a.len++]%=10;
        }    
        return a;
    }
    bool operator == (BIGINT x) {
        if (len!=x.len) return 0;
        for(int i=1; i<=len; i++) 
            if (num[i]!=x.num[i]) return 0;
        return 1;    
    }
    bool operator > (BIGINT x) {
        if (len<x.len) return 0;
        else if (len>x.len) return 1;
        for(int i=len; i>=1; i--) 
            if (num[i]>x.num[i]) return 1;
            else  if (num[i]<x.num[i]) return 0;
        return 0;   
    }
};
int N, M;
int A[85][85];
BIGINT P[85], F[85][85][85];
void POW2 () {
    
    P[0]=1;
    for(int i=1; i<=80; i++) P[i]=P[i-1]*2; 
    
}
int main () {
    
    POW2(); 
    scanf("%d%d", &N, &M);
    for(int i=1; i<=N; i++)
        for(int j=1; j<=M; j++)
            scanf("%d", &A[i][j]);
    BIGINT a=0, b=0, c=0, d=0, ans=0;
    for(int f=1; f<=N; f++) { 
        for(int i=2; i<=M; i++) 
            for(int l=1; l+(M-i)<=M; l++) {  
                int r=l+(M-i); 
                a=F[f][l-1][r]+P[i-1]*A[f][l-1];
                b=F[f][l][r+1]+P[i-1]*A[f][r+1];
                if (a>b) F[f][l][r]=a;
                else F[f][l][r]=b;              
            }   
        c.CLEAR();   
        for(int i=1; i<=M ; i++) {  
            d=F[f][i][i]+P[M]*A[f][i];  
            if (d>c) c=d;
        }
        ans=ans+c;    
    }
    ans.PRINT();
    return 0;
    
}

果然还是要写高精度的么。。。
可怕死了

type
bigint=array [0..100] of longint;
var
a:array [1..100,1..100] of longint;
f:array [1..100,1..100] of bigint;
i,j,m,n,k:longint;
t,s,ans:bigint;

procedure add(var x,y:bigint);
var i,c:longint;
begin
for i:=x[0]+1 to y[0] do x[i]:=0;
for i:=1 to y[0] do x[i]:=x[i]+y[i];
if x[0]<y[0] then x[0]:=y[0];
x[x[0]+1]:=0;
c:=0;
for i:=1 to x[0] do
begin
c:=x[i] div 10;
x[i+1]:=x[i+1]+c;
x[i]:=x[i] mod 10;
end;
if c>0 then x[0]:=x[0]+1;
end;

procedure max(var x,y,z:bigint);
var
i:longint;
begin
if y[0] > z[0] then begin
x := y;
exit;
end
else if y[0] < z[0] then begin
x := z;
exit;
end
else begin
for i:=y[0] downto 1 do begin
if y[i]<z[i] then
begin
x:=z;
exit;
end;
if y[i]>z[i] then
begin
x:=y;
exit;
end;
end;
x:=y;
end;
end;

procedure print(var x:bigint);
var
i:longint;
begin
for i:=x[0] downto 1 do write(x[i]);
if x[0] = 0 then write(0);
writeln;
end;

procedure load (var x:bigint;a:longint);
begin
x[0]:=0;
while a>0 do
begin
x[0]:=x[0]+1;
x[x[0]]:=a mod 10;
a:=a div 10;
end;
end;

begin
readln(n,m);
for k:=1 to n do begin
for j:=1 to m do

read(a[k,j]);

for i:=1 to m do
load(f[i,i],a[k,i]);
for i:=m downto 1 do
for j:=i+1 to m do begin

load(t,a[k,i]);
add(t,f[i+1,j]);
add(t,f[i+1,j]);

load(s,a[k,j]);
add(s,f[i,j-1]);
add(s,f[i,j-1]);

max(f[i,j],s,t);
end;
add(ans,f[1,m]);
end;
add(ans,ans);
print(ans);
end.

c++
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn = 80 + 5;

struct bignum{
    int l; short int w[1000];
    bignum(){
        l = 1; memset(w, 0 , sizeof(w));
    }
    
    bignum(int x){
        l = 0; memset(w, 0 , sizeof(w));
        while(x){
            w[l] = x % 10; x /= 10;
            l++;
        }
    }
    
    bool operator > (bignum x){
        if(l > x.l) return true;
        else 
        if(l == x.l) 
            for(int i = l - 1; i >= 0; i--){
                if(w[i] > x.w[i]) return true;
                if(w[i] < x.w[i]) return false;
            }
        
        return false;
    }
    
    bignum operator + (const bignum& x){
        bignum ans;
        if(l>x.l) ans.l=l;
        else ans.l=x.l;
        
        for(int i = 0; i < ans.l; i++){
            ans.w[i] += w[i] + x.w[i];
            ans.w[i+1] += ans.w[i] / 10;
            ans.w[i] %= 10;
        }
        if(ans.w[ans.l]) ans.l++;
        return ans;
        
    }
    
    bignum operator * (const bignum& x){
        bignum ans;
        ans.l = l + x.l;
        for(int i=0;i<l;i++){
            for(int j=0;j<x.l;j++){
                ans.w[i+j] += w[i] * x.w[j];
                ans.w[i+j+1] += ans.w[i+j] / 10;
                ans.w[i+j] %= 10;
            }
        }
        if(ans.w[ans.l-1]==0) ans.l--;
        return ans;
    }
    bignum operator * (int x){
        bignum ans(x);
        return operator*(ans);
    }
    
    void print(){
        if(l == 0) cout<<0;
        for(int i = l - 1; i >= 0; i--)
            printf("%d", w[i]);
        printf("\n");
    }
    
    
};
int a[maxn]={0};
bignum d[maxn][maxn];//d[i][j]:某一排！！从i到j能够取到的最大值 
int n, m;
int main(){
    cin >> n >> m;
    bignum ans = 0; int x;
    
    bignum mi[83];//m[i]为2的i次幂
    mi[0] = 1;
    for(int i = 1; i <= m; i++){
        mi[i] = mi[i-1];
        mi[i] = mi[i] * 2;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> x; a[j] = x;
        }
        for(int i = 1; i <= m; i++) d[i][i] = mi[m]*a[i];
        for(int l = 1; l < m; l++){
            for(int i = 1; i < m; i++){
                if(i + l > m) break;
                bignum v1 = mi[m - l] * a[i]   + d[i+1][i+l];
                bignum v2 = mi[m - l] *a[i+l] + d[i][i+l-1];
                if(v1>v2) d[i][i+l] = v1;
                else d[i][i+l] = v2;
            }
        }
        ans = ans + d[1][m];
    }
    
    ans.print();
    
    return 0;

}

type tt=record
k:longint;
t:array [0..105] of longint;
end;
var
a:array [0..100] of tt;
f:array [0..100,0..100] of tt;
n,m,i,j,q,u:longint;
x,y,p:tt;
procedure cheng(x:longint; a:tt; var b:tt);
var i:longint;
begin
fillchar(b.t,sizeof(b.t),0);
for i:=1 to a.k do b.t[i]:=a.t[i]*x;
for i:=1 to a.k do begin
inc(b.t[i+1],b.t[i] div 10);
b.t[i]:=b.t[i] mod 10;
end;
b.k:=a.k;
if (b.t[b.k+1]<>0) then inc(b.k);
end;
procedure jia(a,b:tt; var c:tt);
var i:longint;
begin
if (a.k>b.k) then c.k:=a.k else c.k:=b.k;
fillchar(c.t,sizeof(c.t),0);
for i:=1 to c.k do c.t[i]:=b.t[i]+a.t[i];
for i:=1 to c.k do begin
inc(c.t[i+1],c.t[i] div 10);
c.t[i]:=c.t[i] mod 10;
end;
if (c.t[c.k+1]>0) then inc(c.k);
end;
procedure make(var a:tt; p:longint);
begin
fillchar(a.t,sizeof(a.t),0);
a.k:=0;
if (p=0) then begin a.k:=1; a.t[1]:=0; exit; end;
while (p<>0) do begin inc(a.k); a.t[a.k]:=p mod 10; p:=p div 10; end;
end;
procedure print(a:tt);
var i:longint;
begin
for i:=a.k downto 1 do write(a.t[i]);
writeln;
end;
function bj(a,b:tt):boolean;
var i:longint;
begin
if (a.k<b.k) then exit(false);
if (a.k>b.k) then exit(true);
for i:=a.k downto 1 do begin
if (a.t[i]<b.t[i]) then exit(false);
if (a.t[i]>b.t[i]) then exit(true);
end;
exit(false);
end;
begin
read(n,m);
for q:=1 to n do
begin
for i:=1 to m do begin read(u); make(a[i],u); end;
for i:=1 to m do cheng(2,a[i],a[i]);
for i:=1 to m do
for j:=1 to m do begin
fillchar(f[i,j].t,sizeof(f[i,j].t),0);
f[i,j].k:=0; end;
for i:=1 to m do f[i,i]:=a[i];
for i:=2 to m do
for j:=1 to m-i+1 do
begin
cheng(2,f[j,j+i-2],x); jia(x,a[j+i-1],x);
cheng(2,f[j+1,j+i-1],y); jia(y,a[j],y);
if bj(x,y) then f[j,j+i-1]:=x else f[j,j+i-1]:=y;
end;
jia(p,f[1,m],p);
end;
print(p);
end.

#include <cstdio>
#include <iostream>
#include <cstring>

using std::max;

int plusx(int a[],int b[],int c[]){
memset(c,0,sizeof(int)*25);
int len=a[0]>b[0]?a[0]:b[0];
for(int i=1;i<=len;i++){
c[i]+=a[i]+b[i];
c[i+1]+=c[i]/10000;
c[i]%=10000;
}
len++;
while(c[len]==0&&len>1)
len--;
c[0]=len;
}

void plus(int a[],int x){
int len,k;
len=a[1]+x;
k=len/10000;
a[1]=len%10000;
for(int i=2;i<=a[0]||k;i++){
len=a[i]+k;
k=len/10000;
a[i]=len%10000;
}
len=a[0]+1;
while(a[len]==0&&len>1)len--;
a[0]=len;
}

//大于为1 小于或等于为0
int bigger(int a[],int b[]){
if(a[0]!=b[0])
return a[0]>b[0];
int flag;
for(int i=a[0];i>=1;i--)
if(a[i]!=b[i]){
flag=a[i]>b[i];
break;
}
return flag;
}

void output(int a[]){
printf("%d",a[a[0]]);
for(int i=a[0]-1;i>=1;i--)
printf("%04d",a[i]);
}

int main(){
// freopen("game.in","r",stdin);
int n,m;
int a[100][100];
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
int sum[30]={0};
sum[0]=1;
int f[100][100][30];
for(int k=1;k<=n;k++){
memset(f,0,sizeof(f));
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++)
f[i][j][0]=1;
for(int i=1;i<=m;i++){
f[i][1][1]=2*a[k][i];
}
for(int j=2;j<=m;j++)
for(int i=1;i<=m-j+1;i++){
int p1[30]={1},p2[30]={1};
memcpy(p1,f[i+1][j-1],sizeof(p1));
plus(p1,a[k][i]);
memcpy(p2,f[i][j-1],sizeof(p2));
plus(p2,a[k][i+j-1]);
if(bigger(p1,p2))
memcpy(f[i][j],p1,sizeof(p1));
else
memcpy(f[i][j],p2,sizeof(p2));
int temp[30];
plusx(f[i][j],f[i][j],temp);
memcpy(f[i][j],temp,sizeof(temp));
// f[i][j]=max(a[k][i]+f[i+1][j-1],a[k][i+j-1]+f[i][j-1]);
// f[i][j]*=2;
}
int re[30];
plusx(sum,f[1][m],re);
memcpy(sum,re,sizeof(re));
}
output(sum);
return 0;
}

高精度
#include<stdio.h>
using namespace std;
int n,m;
int rec[81][81];
int dp[81][81][21]; //dp[i][j]:maxscore of i~j in one low
int inc[81][81];
int sum[501]={0},suminc=1000000000;

int min(int a,int b)
{
if(a<b) return a;
else return b;
}
void update(int a,int b,int s,int t)
{
int i,cons=20;
for(i=20;i>=inc[s][t];i--)
dp[a][b][i]=dp[s][t][i]*2;

inc[a][b]=inc[s][t];
while(dp[a][b][cons]>=10000 || cons>inc[a][b])
{
dp[a][b][cons-1]+=dp[a][b][cons]/10000;
dp[a][b][cons]%=10000;
cons--;
}
inc[a][b]=min(inc[a][b],cons);
}

void check(int c,int a,int b)
{
int a1=a,a2=b-1,b1=a+1,b2=b,fi=inc[a1][a2],fj=inc[b1][b2],label1[21]={0},label2[21]={0},last1=20,last2=20,i,x;

label1[20]=dp[a1][a2][20];label2[20]=dp[b1][b2][20];
dp[a1][a2][20]+=rec[c][b];
dp[b1][b2][20]+=rec[c][a];

x=20;
while(dp[a1][a2][x]>=10000)
{
label1[x-1]=dp[a1][a2][x-1];
last1=x-1;
dp[a1][a2][x-1]+= dp[a1][a2][x]/10000;
dp[a1][a2][x]%=10000;
x--;
}
if(x<inc[a1][a2]) inc[a1][a2]=x;

x=20;
while(dp[b1][b2][x]>=10000)
{
label2[x-1]=dp[b1][b2][x-1];
last2=x-1;
dp[b1][b2][x-1]+=dp[b1][b2][x]/10000;
dp[b1][b2][x]%=10000;
x--;
}
if(x<inc[b1][b2]) inc[b1][b2]=x;

if(inc[a1][a2]<inc[b1][b2]) update(a,b,a1,a2);
else if(inc[a1][a2]>inc[b1][b2]) update(a,b,b1,b2);
else
{
x=inc[a1][a2];
again:;
if(dp[a1][a2][x]>dp[b1][b2][x]) update(a,b,a1,a2);
else if(dp[a1][a2][x]<dp[b1][b2][x]) update(a,b,b1,b2);
else{if(x!=20) {x++;goto again;} else update(a,b,a1,a2);}
}

for(i=last1;i<=20;i++) dp[a1][a2][i]=label1[i];
for(i=last2;i<=20;i++) dp[b1][b2][i]=label2[i];
inc[a1][a2]=fi;
inc[b1][b2]=fj;

}

int main( )
{

int i,j,k,t,con;
scanf("%d %d",&n,&m);

for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&rec[i][j]);

for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
for(k=1;k<=m;k++)
for(t=0;t<=20;t++)
dp[j][k][t]=0;

for(j=1;j<=m;j++)
{
dp[j][j][20]=rec[i][j]*2;
inc[j][j]=20;
}

for(j=1;j<=m-1;j++)
for(k=1;k<=m-j;k++)
check(i,k,k+j);

con=500;

for(j=20;j>=inc[1][m];j--)
sum[j+480]+=dp[1][m][j];

suminc=min(suminc,inc[1][m]+480);

while(sum[con]>=10000 || con>suminc)
{
sum[con-1]+=sum[con]/10000;
sum[con]%=10000;
con--;
}

suminc=min(con,suminc);

}

for(i=suminc;i<=500;i++)
{
if(i==suminc) printf("%d",sum[i]);
else
{
if(sum[i]>=1000) printf("%d",sum[i]);
else if(sum[i]>=100) printf("0%d",sum[i]);
else if(sum[i]>=10) printf("00%d",sum[i]);
else printf("000%d",sum[i]);
}
}

return 0;
}

解题报告
http://blog.csdn.net/Onlynagesha/article/details/48804093

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN = 85;
const int N = 50;

int m;
int num[MAXN][MAXN], f[MAXN][MAXN][N+10], ming[MAXN][N+10];
int ans[N], bri[N], bri1[N], bri2[N];

void cheng1(int node){
for(int i=1; i<=N; i++)
ming[node][i] = ming[node-1][i] * 2;
for(int i=1; i<=N; i++){
ming[node][i+1] += ming[node][i]/10;
ming[node][i] %= 10;
}

}

void init1(int big){
ming[1][1] = 2;
for(int i=2; i<=big; i++)
cheng1(i);
}

void init2(){
memset(bri, 0, sizeof(bri));
}

void choice(int k, int a, int b){
memset(bri1, 0, sizeof(bri1));
memset(bri2, 0, sizeof(bri2));
int q = m - b + a - 1;
//
for(int i=1; i<=N; i++)
bri1[i] = ming[q][i] * num[k][a-1];
for(int i=1; i<=N; i++){
bri1[i+1] += bri1[i] / 10;
bri1[i] %= 10;

}
for(int i=1; i<=N; i++){
bri1[i] += f[a-1][b][i];
bri1[i+1] += bri1[i] / 10;
bri1[i] %= 10;
}
//
for(int i=1; i<=N; i++)
bri2[i] = ming[q][i] * num[k][b+1];
for(int i=1; i<=N; i++){
bri2[i+1] += bri2[i] / 10;
bri2[i] %= 10;

}
for(int i=1; i<=N; i++){
bri2[i] += f[a][b+1][i];
bri2[i+1] += bri2[i] / 10;
bri2[i] %= 10;
}
//
int flag = 0;
for(int i=N; i>=1; i--){
if(bri1[i] > bri2[i]){
flag = 1;
break;
}
else if(bri1[i] < bri2[i]){
flag = 2;
break;
}
}
if(flag == 1)
for(int i=1; i<=N; i++)
f[a][b][i] = bri1[i];
else
for(int i=1; i<=N; i++)
f[a][b][i] = bri2[i];

}

void Lastcaculate(int k, int a){
memset(bri1, 0, sizeof(bri1));
for(int i=1; i<=N; i++)
bri1[i] = ming[m][i] * num[k][a];
for(int i=1; i<=N; i++){
bri1[i+1] += bri1[i] / 10;
bri1[i] %= 10;
}
for(int i=1; i<=N; i++){
bri1[i] += f[a][a][i];
bri1[i+1] += bri1[i] / 10;
bri1[i] %= 10;
}
//
int flag = 0;
for(int i=N; i>=1; i--){
if(bri[i] > bri1[i])
return;
else if(bri[i] < bri1[i]){
flag = 1;
break;
}

}
if(flag)
for(int i=1; i<=N; i++)
bri[i] = bri1[i];
}

void jia(){
for(int i=1; i<=N; i++){
ans[i] += bri[i];
ans[i+1] += ans[i] / 10;
ans[i] %= 10;
}
}

int main()
{
int n;
scanf("%d%d", &n, &m);
init1(m);
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
scanf("%d", &num[i][j]);
for(int k=1; k<=n; k++){
init2();
for(int i=1; i<=m; i++)
for(int j=m; j>=i; j--)
choice(k, i, j);
for(int i=1; i<=m; i++)
Lastcaculate(k, i);
jia();
}
int len = 1;
for(int i=N; i>=1; i--)
if(ans[i] != 0){
len = i;
break;
}
for(int i=len; i>=1; i--)
printf("%d", ans[i]);
system("pause");

return 0;
}
DP + 高精度 = AC

评测结果

编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 1800 KiB, score = 10

测试数据 #1: Accepted, time = 15 ms, mem = 1800 KiB, score = 10

测试数据 #2: Accepted, time = 15 ms, mem = 1800 KiB, score = 10

测试数据 #3: Accepted, time = 31 ms, mem = 1800 KiB, score = 10

测试数据 #4: Accepted, time = 31 ms, mem = 1800 KiB, score = 10

测试数据 #5: Accepted, time = 62 ms, mem = 1796 KiB, score = 10

测试数据 #6: Accepted, time = 125 ms, mem = 1800 KiB, score = 10

测试数据 #7: Accepted, time = 453 ms, mem = 1796 KiB, score = 10

测试数据 #8: Accepted, time = 609 ms, mem = 1796 KiB, score = 10

测试数据 #9: Accepted, time = 1 ms, mem = 1800 KiB, score = 10

Accepted, time = 1357 ms, mem = 1800 KiB, score = 100
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

struct bignum
{
int l;
short int w[100];
bignum()
{
l=1;
memset(w,0,sizeof(w));
};

bignum(int x)
{
l=0;
memset(w,0,sizeof(w));
while(x!=0)
{
w[l]=x%10;
x/=10;
l++;
}
}

bool operator >(bignum x)
{
if(l>x.l) return true;
else if(l==x.l)
for(int i=l-1;i>=0;i--)
{
if(w[i]>x.w[i]) return true;
else if(w[i]<x.w[i]) return false;
}
return false;
}

bignum operator +(bignum x)
{
bignum ans;
if(l>x.l) ans.l=l;
else ans.l=x.l;
for(int i=0;i<ans.l;i++)
{
ans.w[i]+=w[i]+x.w[i];
ans.w[i+1]+=ans.w[i]/10;
ans.w[i]=ans.w[i]%10;
}
if(ans.w[ans.l]!=0) ans.l++;
return ans;
}

bignum operator*(bignum x)
{
bignum ans;
ans.l=x.l+l;
for(int i=0;i<l;i++)
{
for(int j=0;j<x.l;j++)
{
ans.w[i+j]+=w[i]*x.w[j];
ans.w[i+j+1]+=ans.w[i+j]/10;
ans.w[i+j]%=10;
}
}
if(ans.w[ans.l-1]==0) ans.l--;
return ans;
}

bignum operator*(int d)
{
bignum ans(d);
return operator*(ans);
}

void print()
{
for(int i=l-1;i>=0 ;i--)
printf("%d",w[i]);
printf("\n");
}
};

bignum max(bignum ta,bignum tb)
{
if(ta>tb) return ta;
return tb;
}

int main()
{
static bignum two[80],ans;
int n,m;
scanf("%d%d",&n,&m);
two[0]=1;
for(int i=1;i<=m;i++)
two[i]=two[i-1]*2;
for(int i=0;i<n;i++)
{
int in[80];
bignum dp[80][80];
for(int j=0;j<m;j++)
scanf("%d",&in[j]);
for(int j=0;j<m;j++)
dp[j][j]=two[m]*in[j];
for(int j=m-2;j>=0;j--)
for(int k=j+1;k<m;k++)
dp[j][k]=max(dp[j][k-1]+two[m-k+j]*in[k],dp[j+1][k]+two[m-k+j]*in[j]);
ans=ans+dp[0][m-1];
}
ans.print();
return 0;
}

var x,y,l,i,j,k,m,n,p,q,t,s,max,head,tail:longint;
a:array[0..300,0..300] of longint;
vetex,dist:array[0..300,0..300] of longint;
pre,way:array[0..300] of longint;
ans:longint;
v:array[0..300] of boolean;
ok:boolean;
procedure findway(a:longint);
var i,j:longint;
begin
if ok then exit;
if a=tail then begin ok:=true; exit; end;
for i:=1 to vetex[a,vetex[a,0]] do
if not v[vetex[a,i]] then
begin
v[vetex[a,i]]:=true;
pre[vetex[a,i]]:=a;
findway(vetex[a,i]);
end;
end;
procedure ecc(h,t:longint);
var i,j:longint;
tem,sum:longint;
begin
sum:=0;
for j:=1 to n do
begin
tem:=1000000;
for i:=h to t do
begin
if (dist[way[i],j]<tem) and (dist[way[i],j]<1000000) then tem:=dist[way[i],j]; end; if sum<tem then sum:=tem; end; if sum<ans then ans:=sum; end; procedure floyed; begin for k:=1 to n do for i:=1 to n do for j:=1 to n do if (i<>j) and (i<>k) and (j<>k) and (dist[i,k]+dist[k,j]<dist[i,j]) then
begin
dist[i,j]:=dist[i,k]+dist[k,j];
end;

end;
procedure work;
begin
for i:=1 to p do
for j:=i to p do
if (dist[way[i],way[j]]<=s) and (dist[way[i],way[j]]<1000000) then ecc(i,j); end; begin ans:=10000000; read(n,s); for i:=1 to n do for j:=1 to n do dist[i,j]:=1000000; for i:=1 to n do dist[i,i]:=0; for i:=1 to n-1 do begin read(x,y,l); dist[x,y]:=l; dist[y,x]:=l; inc(vetex[x,0]); vetex[x,vetex[x,0]]:=y; inc(vetex[y,0]); vetex[y,vetex[y,0]]:=x; end; floyed; for i:=1 to n do for j:=i+1 to n do if (dist[i,j]>max) and (dist[i,j]<100000) then
begin
max:=dist[i,j];
head:=i;
tail:=j;
end;
findway(head);
pre[head]:=0;
k:=tail;
repeat
inc(p);
way[p]:=k;
k:=pre[k];
until k=0;
work;
writeln(ans);
end.

NOIP2014赛前AC留念
（查了一上午的高精度……赛前还是要巩固一下基础算法啊……）
type hugeint=record
num:array[1..120] of integer;
len:longint;
end;
var ans:hugeint;
f:array[1..80,1..80,1..80] of hugeint;
n,m,i,j,k:longint;
tip,tt:array[0..80] of hugeint;
a:array[1..80,1..80] of longint;
zz:hugeint;

function add(a,b:hugeint):hugeint;
var temp,i:longint;
begin
for i:=1 to 120 do add.num[i]:=0;
if a.len>b.len then temp:=a.len
else temp:=b.len;

for i:=1 to temp do
add.num[i]:=a.num[i]+b.num[i];

for i:=1 to temp do
if add.num[i]>=10 then
begin
add.num[i+1]:=add.num[i+1]+add.num[i] div 10;
add.num[i]:=add.num[i] mod 10;
end;

if add.num[temp+1]>0 then add.len:=temp+1
else add.len:=temp;
zz:=add;
end;

function plus(k:longint):hugeint;
var i,j:longint;
begin
for i:=1 to 120 do plus.num[i]:=0;
plus.len:=1;
plus.num[1]:=1;
zz:=plus;
for i:=1 to k do
begin
for j:=1 to plus.len do
plus.num[j]:=plus.num[j]*2;
zz:=plus;
for j:=1 to plus.len do
begin
plus.num[j+1]:=plus.num[j+1]+plus.num[j] div 10;
plus.num[j]:=plus.num[j] mod 10;
end;
if plus.num[plus.len+1]>0 then inc(plus.len);
end;
zz:=plus;
end;

function cheng(k:longint;p:hugeint):hugeint;
var i,qq:longint;
s:string;
begin
zz:=p;
for i:=1 to p.len do
p.num[i]:=p.num[i]*k;
str(k,s);
qq:=length(S);
for i:=1 to p.len+qq do
begin
if p.num[i]>=10 then
begin
p.num[i+1]:=p.num[i+1]+p.num[i] div 10;
p.num[i]:=p.num[i] mod 10;
end;
end;

for i:=p.len+qq+2 downto p.len do
if p.num[i]>0 then
begin
p.len:=i;
break;
end;
cheng:=p;
zz:=p;
end;

function max(a,b:hugeint):hugeint;
var i:longint;
begin
if a.len>b.len then exit(a);
if b.len>a.len then exit(b);
for i:=a.len downto 1 do
begin
if a.num[i]>b.num[i] then exit(a);
if a.num[i]<b.num[i] then exit(b);
end;
exit(a);
end;

begin
//assign(input,'t5.in');
//assign(output,'t5.out');
//reset(input);
//rewrite(output);
readln(n,m);
for i:=1 to n do
for j:=1 to m do read(a[i,j]);
tip[0].len:=1;
tip[0].num[1]:=0;
for i:=1 to m do tip[i]:=plus(i);
for i:=1 to n do
begin
tt[i].len:=0;
f[i,1,m].len:=0;
f[i,1,m].num[1]:=0;
for j:=1 to m do
for k:=m downto j do
if m-k+j-1>0 then
begin
f[i,j,k].len:=0;
f[i,j,k].num[1]:=0;
if j-1>0 then
f[i,j,k]:=max(add(f[i,j-1,k],cheng(a[i,j-1],tip[m-k+j-1])),f[i,j,k]);
if k+1<=m then f[i,j,k]:=max(add(f[i,j,k+1],cheng(a[i,k+1],tip[m-k+j-1])),f[i,j,k]);
end;
zz:=cheng(a[i,1],tip[1]);
zz:=cheng(a[i,3],tip[m]);
zz:=f[i,2,3];
for j:=1 to m do
tt[i]:=max(add(f[i,j,j],cheng(a[i,j],tip[m])),tt[i]);
end;
for i:=1 to n do
ans:=add(ans,tt[i]);
for i:=ans.len downto 1 do
write(ans.num[i]);
writeln;
//close(input);
//close(output);
end.

#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
struct bign
{
int dig,num[40];
void init()
{
dig=1;
memset(num,0,sizeof(num));
}
}f[90][90],_pow[90],ans;
bign two=(bign){1,{0,2}};
bign operator + (bign a,bign b)
{
int i;
bign c;
memset(c.num,0,sizeof(c.num));
for(i=1;i<=(c.dig=max(a.dig,b.dig));i++)
{
c.num[i]+=a.num[i]+b.num[i];
c.num[i+1]=c.num[i]/10;
c.num[i]%=10;
}
if(c.num[c.dig+1]>0)
c.dig++;
return c;
}
bign operator * (bign a,bign b)
{
int i,j;
bign c;
memset(c.num,0,sizeof(c.num));
for(i=1;i<=a.dig;i++)
for(j=1;j<=b.dig;j++)
c.num[i+j-1]+=a.num[i]*b.num[j];
for(i=1;i<=(c.dig=a.dig+b.dig-1);i++)
{
c.num[i+1]+=c.num[i]/10;
c.num[i]%=10;
}
if(c.num[c.dig+1]>0)
c.dig++;
return c;
}
bign operator * (bign a,int b)
{
int i;
bign c;
memset(c.num,0,sizeof(c.num));
for(i=1;i<=a.dig;i++)
c.num[i]+=a.num[i]*b;
for(c.dig=1;;c.dig++)
{
c.num[c.dig+1]+=c.num[c.dig]/10;
c.num[c.dig]%=10;
if(c.num[c.dig+1]==0)
break;
}
return c;
}
bign _max(bign a,bign b)
{
int i;
if(a.dig>b.dig)
return a;
if(a.dig<b.dig)
return b;
for(i=a.dig;i>=1;i--)
if(a.num[i]>b.num[i])
return a;
else
if(a.num[i]<b.num[i])
return b;
return a;
}
main()
{
int n,m,a[90],i,j,r,c;
cin>>n>>m;
_pow[0]=(bign){1,{0,1}};
for(i=1;i<=m;i++)
_pow[i]=_pow[i-1]*two;
for(r=1;r<=n;r++)
{
for(c=1;c<=m;c++)
cin>>a[c];
for(i=1;i<=m;i++)
for(j=1;j<=m;j++)
f[i][j].init();
for(i=1;i<=m;i++)
f[i][i]=_pow[m]*a[i];
for(i=m-1;i>=1;i--)
for(j=i+1;j<=m;j++)
f[i][j]=_max(f[i+1][j]+_pow[m-j+i]*a[i],f[i][j-1]+_pow[m-j+i]*a[j]);
ans=ans+f[1][m];
}
for(i=ans.dig;i>=1;i--)
cout<<ans.num[i];
}

恶心的高精度。。