区间DP+高精度

不得不说于高精度挂钩的题目都比较毒瘤....

对于这道题,首先可以发现对于每一行的取法对其他行是没有影响的.
于是我们就可以单独考虑每一行,让每一行取到最大值,在总体求和即可.

于是我们设dp[i][j]表示当前区间为[i,j]的最大分数.
由于每一次都只在该行的行首和行尾取数,于是[i,j]可以从[i-1,j]或[i,j+1]转移过来.
于是就有dp[i][j]=max(dp[i-1][j]+Map[i-1]2^(m+i-j-1),dp[i][j+1]+Map[j+1]2^(m+i-j-1));
其中Map[i]代表该行的第i个数.

然后就要考虑毒瘤高精度运算,自然是套模板呀....
这题竟然还要用压位高精

时间复杂度 $O(nm^2)$

C++ 代码

//相信奇迹的人,本身就和奇迹一样了不起.
#include<bits/stdc++.h>
#define SIZE 1010
#define N 85
using namespace std;
const int mod=1e4;//压四位即可
struct hugeint{
    int num[SIZE],len;
}dp[N][N],power_2[N],ans;
int n,m,Map[N];
hugeint max (const hugeint &a,const hugeint &b){//比较函数
        if(a.len>b.len)
            return a;
        if(a.len<b.len)
            return b;
        for(int i=a.len;i>=1;i--){
            if(a.num[i]>b.num[i])
                return a;
            if(a.num[i]<b.num[i])
                return b;
        }
        return a;
    }
hugeint operator + (const hugeint &a,const hugeint &b){//高精加
    hugeint c;
    memset(c.num,0,sizeof(c.num));
    c.len=max(a.len,b.len);
    for(int i=1;i<=c.len;i++){
        c.num[i]+=(a.num[i]+b.num[i]);
        c.num[i+1]+=c.num[i]/mod;
        c.num[i]%=mod;
    }
    if(c.num[c.len+1])
        c.len++;
    return c;
}
hugeint operator * (const hugeint &a,const int &b){//高精乘
    hugeint c;
    memset(c.num,0,sizeof(c.num));
    c.len=a.len;
    int temp=0;
    for(int i=1;i<=c.len;i++){
        c.num[i]=(a.num[i]*b+temp);
        temp=c.num[i]/mod;
        c.num[i]%=mod;
    }
    while(temp){
        c.num[++c.len]=temp%mod;
        temp/=mod;
    }
    return c;
}
inline void init()//预处理2的幂次
{
    power_2[0].num[1]=1,power_2[0].len=1;
    for(int i=1;i<=m+2;i++)
        power_2[i]=power_2[i-1]*2;
}
inline void print(hugeint a)//输出
{
    printf("%d",a.num[a.len]);
    for(int i=a.len-1;i>=1;i--){//压位的输出有讲究
        if(!a.num[i]){
            printf("0000");
            continue;
        }
        for(int j=10;j*a.num[i]<mod;j*=10)
            printf("0");
        printf("%d",a.num[i]);
    }
    printf("\n");
}
int main()
{
    //freopen("game.in","r",stdin),freopen("game.out","w",stdout);
    scanf("%d %d",&n,&m);
    init();
    while(n--){//处理每一行
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=m;i++)
            scanf("%d",&Map[i]);
        for(int i=1;i<=m;i++)
            for(int j=m;j>=i;j--){//注意从大区间dp到小区间
                dp[i][j]=max(dp[i][j],dp[i-1][j]+power_2[m+i-j-1]*Map[i-1]);
                dp[i][j]=max(dp[i][j],dp[i][j+1]+power_2[m+i-j-1]*Map[j+1]);
            }
        hugeint MAX;
        memset(MAX.num,0,sizeof(MAX.num));
        MAX.len=0;
        for(int i=1;i<=m;i++)//因为每一个数都可能成为最后取的数,所以要循环找最大的
            MAX=max(MAX,dp[i][i]+power_2[m]*Map[i]);
        ans=ans+MAX;//累加答案
    }
    print(ans);
    return 0;
}