P1005-矩阵取数游戏

刺骨的言语ヽ痛彻心扉 2023-06-01 08:52 21阅读 0赞

1 #include <bits/stdc++.h>
      2 #define _for(i,a,b) for(int i = (a);i < b;i ++)
      3 #define _rep(i,a,b) for(int i = (a);i > b;i --)
      4 #define INF 0x3f3f3f3f
      5 typedef long long ll;
      6 using namespace std;
      7 inline ll read()
      8 {
      9     ll ans = 0;
     10     char ch = getchar(), last = ' ';
     11     while(!isdigit(ch)) last = ch, ch = getchar();
     12     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
     13     if(last == '-') ans = -ans;
     14     return ans;
     15 }
     16 inline void write(ll x)
     17 {
     18     if(x < 0) x = -x, putchar('-');
     19     if(x >= 10) write(x / 10);
     20     putchar(x % 10 + '0');
     21 }
     22 const int maxn = 50;
     23 class HP
     24 {
     25     public : int len,s[maxn]; HP() {(*this) = 0;};
     26     HP(int inte) {(*this)=inte;}; HP(const char*str) {(*this)=str;};
     27     friend ostream& operator << (ostream &cout,const HP &x);
     28     HP operator = (int inte); HP operator = (const char*str);
     29     HP operator * (const HP &b);HP operator + (const HP &b);
     30     HP operator - (const HP &b);HP operator / (const HP &b);
     31     HP operator % (const HP &b);int Compare(const HP &b);
     32     bool operator < (const HP &b);
     33 };
     34 
     35 ostream& operator << (ostream &cout,const HP &x)
     36 {
        for(int i = x.len;i >= 1;i --) cout<<x.s[i];return cout;}
     37 
     38 HP HP::operator = (const char *str)
     39 {
     40     len = strlen(str);
     41     for(int i = 1;i <= len;i ++) s[i] = str[len-i]-'0';
     42     return (*this);
     43 }
     44 
     45 HP HP::operator = (int inte)
     46 {
     47     if(inte==0) {len = 1;s[1] = 0;return (*this);};
     48     for(len = 0;inte > 0;) {s[++len] = inte%10;inte /= 10;};
     49     return (*this);
     50 }
     51 
     52 HP HP::operator * (const HP&b)
     53 {
     54     int i,j;HP c;c.len = len+b.len;
     55     for(i = 1;i <= c.len;i ++) c.s[i] = 0;
     56     for(i = 1;i <=len;i ++) for(j = 1;j <=b.len;j ++) c.s[i+j-1]+=s[i]*b.s[j];
     57     for(i = 1;i < c.len;i ++) {c.s[i+1]+=c.s[i]/10;c.s[i]%=10;}
     58     while(c.s[i]) {c.s[i+1]=c.s[i]/10;c.s[i]%=10;i ++;}
     59     while(i>1&&!c.s[i]) i--;c.len = i;
     60     return c;
     61 }
     62 
     63 HP HP::operator+(const HP &b)
     64 {
     65     int i;HP c;c.s[1] = 0;
     66     for(i = 1;i <=len || i<=b.len || c.s[i];i ++)
     67     {
     68         if(i<=len) c.s[i]+=s[i];
     69         if(i<=b.len) c.s[i]+=b.s[i];
     70         c.s[i+1]=c.s[i]/10;c.s[i]%=10;
     71     }
     72     c.len = i-1;if(c.len==0) c.len = 1;
     73     return c;
     74 }
     75 
     76 HP HP::operator-(const HP&b)
     77 {
     78     int i, j;HP c;
     79     for(i = 1,j = 0;i <= len;i ++)
     80     {
     81         c.s[i] = s[i]-j;if(i<=b.len) c.s[i]-=b.s[i];
     82         if(c.s[i]<0){j = 1;c.s[i]+=10;}else j = 0;
     83     }
     84     c.len = len;while(c.len>1&&!c.s[c.len]) c.len--;
     85     return c;
     86 }
     87 
     88 int HP::Compare(const HP &y)
     89 {
     90     if(len>y.len) return 1;
     91     if(len<y.len) return -1;
     92     int i = len;
     93     while((i>1)&&(s[i]==y.s[i])) i--;
     94     return s[i]-y.s[i];
     95 }
     96 
     97 bool HP::operator < (const HP &y)
     98 {
     99     if(this->Compare(y)>=0)    return false;
    100     return true;
    101 }
    102 
    103 HP HP::operator / (const HP&b)
    104 {
    105     int i,j;HP d(0),c;
    106     for(i = len;i > 0;i --)
    107     {
    108         if(!(d.len==1 && d.s[1]==0))
    109             {
        for(j = d.len;j > 0;j --) d.s[j+1]=d.s[j];++d.len;}
    110         d.s[1] = s[i]; c.s[i] = 0;
    111         while((j = d.Compare(b))>=0)
    112             {d=d-b;c.s[i]++;if(j==0) break;}
    113     }
    114     c.len = len;while((c.len>1)&&(c.s[c.len]==0)) c.len--;
    115     return c;
    116 }
    117 
    118 HP HP::operator%(const HP&b)
    119 {
    120     int i,j;HP d(0);
    121     for(i = len;i > 0;i --)
    122     {
    123         if(!(d.len==1 && d.s[1]==0))
    124         {
        for(j = d.len;j > 0;j --) d.s[j+1]=d.s[j];++d.len;}
    125     d.s[1] = s[i];
    126     while((j = d.Compare(b))>=0) {d = d-b;if(j==0)break;}
    127     }
    128     return d;
    129 }
    130 
    131 
    132 int n,m; 
    133 HP A[81][81];
    134 HP f[81][81][81];
    135 HP base[81];
    136 
    137 void Base()
    138 {
    139     base[0] = 1,base[1] = 2;
    140     _for(i,2,81)
    141         base[i] = base[i-1]*2;
    142 }
    143 int main()
    144 {
    145     ios::sync_with_stdio(false);
    146     Base();
    147     n = read(), m = read();
    148     _for(i,1,n+1)
    149         _for(j,1,m+1)
    150             A[i][j] = read();
    151     
    152     _for(i,1,n+1)
    153         _rep(len,m,0)
    154             _for(l,1,m-len+2)
    155             {
    156                 int r = l+len-1;
    157                 if(f[i][l-1][r]+A[i][l-1]*base[m-r+l-1]
    158                 <  f[i][l][r+1]+A[i][r+1]*base[m-r+l-1])
    159                     f[i][l][r] = f[i][l][r+1]+A[i][r+1]*base[m-r+l-1];
    160                 else
    161                     f[i][l][r] = f[i][l-1][r]+A[i][l-1]*base[m-r+l-1];
    162             }
    163     
    164     HP ans;
    165     ans = 0;
    166     _for(i,1,n+1)
    167     {
    168         HP tmp;
    169         tmp = 0;
    170         _for(j,1,m+1)
    171             if(tmp < f[i][j][j]+A[i][j]*base[m])
    172                 tmp = f[i][j][j]+A[i][j]*base[m];
    173         ans = ans+tmp;
    174     }
    175     cout << ans << endl;
    176     return 0;
    177 }

转载于:https://www.cnblogs.com/Asurudo/p/11403875.html