AC日记——矩阵取数游戏 洛谷 P1005

矩阵取数游戏

思路：

　　dp+高精；

代码：

#include <bits/stdc++.h>

using namespace std;

#define ll long long

struct Int {

    int len;

    char ai[];

    Int()

    {

        len=,ai[]=;

    }

    void Count(int pos)

    {

        len++;

        if(pos/) Count(pos/);

    }

    void operator=(int pos_)

    {

        int pos=pos_;

        len=,Count(pos);

        for(int i=;i<len;i++) ai[i]=pos%,pos/=;

    }

    bool operator<(const Int pos)const

    {

        if(len<pos.len) return true;

        else if(len>pos.len) return false;

        for(int i=len-;i>=;i--)

        {

            if(ai[i]<pos.ai[i]) return true;

            else if(ai[i]>pos.ai[i]) return false;

        }

        return false;

    }

    Int operator*(const int pos)const

    {

        ll tmp=;Int res;res.len=len;

        for(int i=;i<len;i++) tmp+=ai[i]*pos,res.ai[i]=tmp%,tmp/=;

        while(tmp) res.ai[res.len++]=tmp%,tmp/=;

        return res;

    }

    Int operator+(const Int pos)const

    {

        ll tmp=;Int res;res.len=max(len,pos.len);

        for(int i=;i<res.len;i++) tmp+=(i<len?ai[i]:)+(i<pos.len?pos.ai[i]:),res.ai[i]=tmp%,tmp/=;

        while(tmp) res.ai[res.len++]=tmp%,tmp/=;

        return res;

    }

    void print()

    {

        for(int i=len-;i>=;i--) putchar(ai[i]+'');

    }

};

Int dp[][],ans,ci[][];

int ai[][],n,m;

Int max(Int a,Int b)

{

    if(a<b) return b;

    else return a;

}

int main()

{

    freopen("data.txt","r",stdin);

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)

    {

        for(int v=;v<=m;v++) scanf("%d",&ai[i][v]),ci[i][v]=ai[i][v];

    }

    for(int i=;i<=n;i++)

    {

        for(int v=;v<=m;v++) dp[v][v]=ai[i][v]*;

        for(int k=;k<m;k++)

        {

            for(int v=;v+k<=m;v++)

            {

                int l=v,r=v+k;

                dp[l][r]=max((dp[l+][r]+ci[i][l])*,(dp[l][r-]+ci[i][r])*);

            }

        }

        ans=dp[][m]+ans;

    }

    ans.print();

    return ;

}