方程:
$f_{i,j}=\max\{f_{i-1,j}+2^{m+i-j-1}*a_{i-1},f_{i,j+1}+2^{m+i-j-1}*a_{j+1}\}$
还需要打高精。。。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
using namespace std;
const int N=83;
template<class o>
inline void qr(o &x)
{
x=0;char c=gc;
while(c<'0'||c>'9')c=gc;
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
}
void qw(int x)
{
if(x/10)qw(x/10);
putchar(x%10+48);
}
struct node
{
int a[105];
node(){memset(a,0,sizeof(a));}
node operator +(const node b)const
{
node c;c.a[0]=max(a[0],b.a[0]);
for(int i=1;i<=c.a[0];i++)
c.a[i]=b.a[i]+a[i];
for(int i=1;i<c.a[0];i++)
c.a[i+1]+=c.a[i]/10,c.a[i]%=10;
int i=c.a[0];
while(c.a[i]/10)c.a[i+1]+=c.a[i]/10,c.a[i]%=10,++i;
c.a[0]=i;
return c;
}
node operator *(const node b)const
{
node c;c.a[0]=a[0]+b.a[0]-1;
for(int i=1;i<=a[0];i++)
for(int j=1;j<=b.a[0];i++)
c.a[i+j-1]+=a[i]*b.a[j];
for(int i=1;i<c.a[0];i++)
c.a[i+1]+=c.a[i]/10,c.a[i]%=10;
int i=c.a[0];
while(c.a[i]/10)c.a[i+1]+=c.a[i]/10,c.a[i]%=10,++i;
c.a[0]=i;
return c;
}
node operator *(const int x)const
{
node c;c.a[0]=a[0];
for(int i=1;i<=c.a[0];i++)
c.a[i]=a[i]*x;
for(int i=1;i<c.a[0];i++)
c.a[i+1]+=c.a[i]/10,c.a[i]%=10;
int i=c.a[0];
while(c.a[i]/10)c.a[i+1]+=c.a[i]/10,c.a[i]%=10,++i;
c.a[0]=i;
return c;
}
bool operator <(const node b)const
{
if(a[0]<b.a[0])return 1;
else if(a[0]>b.a[0])return 0;
for(int i=a[0];i;i--)
{
if(a[i]<b.a[i])return 1;
if(a[i]>b.a[i])return 0;
}
return 1;
}
}bin[N],f[N][N],g[N][N];
int a[N][N];
int main()
{
int n,m;qr(n),qr(m);bin[0].a[0]=1;bin[0].a[1]=1;
for(int i=1;i<=m;i++)
bin[i]=bin[i-1]+bin[i-1];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
qr(a[i][j]);
node ans;
for(int p=1;p<=n;p++)
{
memcpy(f,g,sizeof(g));
for(int k=m-1;k;k--)
for(int i=1;i<=m-k+1;i++)
{
int j=i+k-1;
f[i][j]=max(f[i-1][j]+bin[m-k]*a[p][i-1],f[i][j+1]+bin[m-k]*a[p][j+1]);
}
node s1,s2;
for(int i=1;i<=m;i++)
{
s2=f[i][i]+bin[m]*a[p][i];
if(s1<s2)s1=s2;
}
ans=ans+s1;
}
for(int i=ans.a[0];i;i--)
printf("%d",ans.a[i]);
puts("");
return 0;
}
最后一次更新于2020-05-13
0 条评论