首页 > 代码库 > AC日记——矩阵取数游戏 洛谷 P1005

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

矩阵取数游戏

 

思路:

  dp+高精;

 

代码:

#include <bits/stdc++.h>using namespace std;#define ll long longstruct Int {    int len;    char ai[300];    Int()    {        len=1,ai[0]=0;    }    void Count(int pos)    {        len++;        if(pos/10) Count(pos/10);    }    void operator=(int pos_)    {        int pos=pos_;        len=0,Count(pos);        for(int i=0;i<len;i++) ai[i]=pos%10,pos/=10;    }    bool operator<(const Int pos)const    {        if(len<pos.len) return true;        else if(len>pos.len) return false;        for(int i=len-1;i>=0;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=0;Int res;res.len=len;        for(int i=0;i<len;i++) tmp+=ai[i]*pos,res.ai[i]=tmp%10,tmp/=10;        while(tmp) res.ai[res.len++]=tmp%10,tmp/=10;        return res;    }    Int operator+(const Int pos)const    {        ll tmp=0;Int res;res.len=max(len,pos.len);        for(int i=0;i<res.len;i++) tmp+=(i<len?ai[i]:0)+(i<pos.len?pos.ai[i]:0),res.ai[i]=tmp%10,tmp/=10;        while(tmp) res.ai[res.len++]=tmp%10,tmp/=10;        return res;    }    void print()    {        for(int i=len-1;i>=0;i--) putchar(ai[i]+0);    }};Int dp[81][81],ans,ci[81][81];int ai[81][81],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=1;i<=n;i++)    {        for(int v=1;v<=m;v++) scanf("%d",&ai[i][v]),ci[i][v]=ai[i][v];    }    for(int i=1;i<=n;i++)    {        for(int v=1;v<=m;v++) dp[v][v]=ai[i][v]*2;        for(int k=1;k<m;k++)        {            for(int v=1;v+k<=m;v++)            {                int l=v,r=v+k;                dp[l][r]=max((dp[l+1][r]+ci[i][l])*2,(dp[l][r-1]+ci[i][r])*2);            }        }        ans=dp[1][m]+ans;    }    ans.print();    return 0;}

 

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