和奶牛那个题很像,每一行状态互不影响,也就是求 n 遍DP
不过高精度非常恶心,第一次写,调了我一上午。
——代码
#include <cstdio>
#include <cstring>
#include <iostream> struct Big_int
{
int s[], idx;
Big_int()
{
idx = ;
memset(s, , sizeof(s));
}
}; int n, m;
Big_int ans, a[], f[][]; inline void clear(Big_int &x)
{
x.idx = ;
memset(x.s, , sizeof(x.s));
} inline Big_int Big(int x)
{
Big_int ret;
while(x)
{
ret.s[ret.idx] = x % ;
x /= ;
ret.idx++;
}
return ret;
} inline bool operator > (const Big_int x, const Big_int y)
{
int i;
if(x.idx > y.idx) return ;
else if(x.idx < y.idx) return ;
else for(i = x.idx - ; i >= ; i--)
if(x.s[i] > y.s[i]) return ;
else if(x.s[i] < y.s[i]) return ;
} inline Big_int Max(const Big_int x, const Big_int y)
{
return x > y ? x : y;
} inline int max(int x, int y)
{
return x > y ? x : y;
} inline Big_int operator + (const Big_int x, const Big_int y)
{
int i;
Big_int ret;
ret.idx = max(x.idx, y.idx) + ;
for(i = ; i < ret.idx; i++)
{
ret.s[i] += x.s[i] + y.s[i];
ret.s[i + ] += ret.s[i] / ;
ret.s[i] %= ;
}
while(!ret.s[ret.idx - ] && ret.idx > ) ret.idx--;
return ret;
} inline Big_int operator * (const Big_int x, const Big_int y)
{
int i, j;
Big_int ret;
ret.idx = x.idx + y.idx;
for(i = ; i < x.idx; i++)
for(j = ; j < y.idx; j++)
{
ret.s[i + j] += x.s[i] * y.s[j];
ret.s[i + j + ] += ret.s[i + j] / ;
ret.s[i + j] %= ;
}
while(!ret.s[ret.idx - ] && ret.idx > ) ret.idx--;
return ret;
} inline void print(const Big_int x)
{
int i;
if(!x.idx) printf("");
else for(i = x.idx - ; i >= ; i--) printf("%d", x.s[i]);
puts("");
} inline int read()
{
int x = , f = ;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -;
for(; isdigit(ch); ch = getchar()) x = (x << ) + (x << ) + ch - '';
return x * f;
} inline Big_int dp(int x, int y, Big_int z)
{
if(f[x][y].idx) return f[x][y];
if(x == y) return f[x][y] = a[x] * z;
else return f[x][y] = Max(dp(x + , y, z * Big()) + a[x] * z, dp(x, y - , z * Big()) + a[y] * z);
} int main()
{
int i, j;
n = read();
m = read();
while(n--)
{
for(i = ; i <= m; i++) a[i] = Big(read());
for(i = ; i <= m; i++)
for(j = ; j <= m; j++)
clear(f[i][j]);
ans = ans + dp(, m, Big());
}
print(ans);
return ;
}