题解 P1005 【矩阵取数游戏】

· · 题解

一.有关dp方程

由于此题中每一行的取数情况都不影响另外几行，所以我们可以把每一行都分开进行动态规划，把二维压缩为一维。

设dp[l][r]为区间[l,r]的最大得分

dp[l][r]$=$max(dp[l+1][r]+2^{m-(r-l)}*a[l],dp[l][r-1]+2^{m-(r-l)}*a[r])

由于题目中说每次只能取行首或行尾，所以转移方程就“枚举”取行首和取行尾时的情况，并比较哪个更大，作为dp[l][r]的最优解

可以通过循环来进行动态规划，但由于变量控制比较麻烦，所以用记忆化搜索 代码如下： ``` long long solve(int l,int r) { if(dp[l][r]) return dp[l][r]; if(l==r) { dp[l][r]=a[l]*pow(2,m-(r-l)); return dp[l][r]; } dp[l][r]=max(solve(l+1,r)+pow(2,m-(r-l))*a[l],solve(l,r-1)+pow(2,m-(r-l))*a[r]); return dp[l][r]; } ``` 由于这题的$m<=80$，所以肯定有$x*2^{80}$的情况，用long long必定不行。所以我们用高精 ### 二.有关高精 由于此题中需要进行高精运算的数众多，所以我们用结构体来，节约代码。 在本题中，作者使用的是压位高精。 一般的高精度是10进制，而压位高精则是$10^b$进制。压位高精更快。 注：作者采用的$b=8

不过在高精时，我们要注意初始化

我们用p[i]来保存2^i，从而去除重复的计算

代码如下：

#include<bits/stdc++.h>
using namespace std;
long long base=100000000;
struct BigInt
{
    long long w[85];
    int len;
};
void write(BigInt ans)
{
    cout<<ans.w[ans.len];
    for(int i=ans.len-1;i>=1;--i)
    {
        long long x=ans.w[i],lenc=0;
        while(x)
        {
            lenc++;
            x/=10;
        }
        for(int j=1;j<=8-lenc;++j)
            cout<<0;
        cout<<ans.w[i];
    }
}
BigInt operator +(const BigInt &a,const BigInt &b)
{
    BigInt c;
    c.len=max(a.len,b.len)+1;
    for(int i=1;i<=c.len;++i)
        c.w[i]=0;
    for(int i=1;i<=c.len;++i)
    {
        c.w[i]+=a.w[i]+b.w[i];
        c.w[i+1]+=c.w[i]/base;
        c.w[i]%=base;
    }
    while(c.w[c.len]==0 && c.len>1)
        c.len--;
    return c;
}
BigInt operator *(const BigInt &a,const BigInt &b)
{
    BigInt c;
    c.len=a.len+b.len;
    for(int i=1;i<=c.len;++i)
        c.w[i]=0;
//  write(a); cout<<" "; write(b); cout<<endl; cout<<a.w[1]*b.w[1]<<endl;
    for(int i=1;i<=a.len;++i)
        for(int j=1;j<=b.len;++j)
        {
            c.w[i+j-1]+=a.w[i]*b.w[j];
            c.w[i+j]+=c.w[i+j-1]/base;
            c.w[i+j-1]%=base;
        }
    while(c.w[c.len]==0 && c.len>1)
        c.len--;
//  write(c); cout<<endl;
    return c;
}
BigInt max(const BigInt &a,const BigInt &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.w[i]>b.w[i]) return a;
        else if(a.w[i]<b.w[i]) return b;
    return a;
}
BigInt pow(int n,int b)
{
    BigInt ans,x;
    ans.w[1]=1; ans.len=1;
    x.w[1]=n; x.len=1;
    for(int i=1;i<=b;++i)
        ans=ans*x;
    return ans;
}
BigInt ctime(BigInt a,int b)
{
    BigInt ans=a;
    for(int i=ans.len+1;i<=ans.len+3;++i)
        ans.w[i]=0;
    for(int i=1;i<=ans.len;++i)
        ans.w[i]*=b;
    for(int i=1;i<=ans.len;++i)
    {
        ans.w[i+1]+=ans.w[i]/base;
        ans.w[i]%=base;
    }
    while(ans.w[ans.len+1]>0)
    {
        ans.len++;
        ans.w[ans.len+1]+=ans.w[ans.len]/base;
        ans.w[ans.len]%=base;
    }
 //   write(a); cout<<" "<<b<<" "; write(ans); cout<<endl;
    return ans;
}
BigInt dp[85][85],ans,p[85];
int a[85];
int m;
BigInt solve(int l,int r)
{
    if(dp[l][r].len>=1) return dp[l][r];
    if(l==r)
    {
        dp[l][r]=ctime(pow(2,m-(r-l)),a[l]);
        return dp[l][r];
    }
//  cout<<l<<" "<<r<<" "<<a[l]<<endl;
//  write(ctime(pow(2,m-(r-l)),a[l])); cout<<endl;
//  write(ctime(pow(2,m-(r-l)),a[r])); cout<<endl;
//  cout<<endl<<endl<<endl;
    dp[l][r]=max(solve(l+1,r)+ctime(p[m-(r-l)],a[l]),solve(l,r-1)+ctime(p[m-(r-l)],a[r]));
    return dp[l][r];
}
int main()
{
    int n;
    cin>>n>>m;
    ans.w[1]=0; ans.len=1; p[0].len=1; p[0].w[1]=1;
    for(int i=1;i<=m;++i)
        p[i]=ctime(p[i-1],2);
 //   write(p[30]);
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
            for(int k=1;k<=m;++k)
                dp[j][k].len=0;
        for(int j=1;j<=m;++j)
            cin>>a[j];
        ans=ans+solve(1,m);
//      write(ans); cout<<endl;
    }
    write(ans);
    return 0;
}