前排着重强调 这里的sizeof 必须搞M
不能sizeof c c是形参,大小只有1 (因此,debug一小时)
memcpy(c,b,sizeof ss);
—
%10 /10的写法要1000ms 压8位只用100ms, 记得开ll,其实复杂度瓶颈在M的大小上,,
M不变,改变%数和/数 不影响时间,,只不过%数大了能减小 M的规模从而降低时间
从此高精度的 +和* 不用vector
数组的高精度除法 也能压位吗,,,,,,
好像高除用的不是很多,,
#include<bits/stdc++.h>
using namespace std;
const int N=90,M=5;
typedef long long ll;
int f[N][N][M];
int n,m;
int ss[M];
void add(int c[],int a[],int b[]){
ll t=0;
for(int i=0;i<M;i++){
t+=a[i]+b[i];
c[i]=t%100000000;
t/=100000000;
}
}
void mul(int c[],int a[],int b){
ll t=0;
for(int i=0;i<M;i++){
t+=(ll)a[i]*b;
c[i]=t%100000000;
t/=100000000;
}
}
void maxv(int c[],int a[],int b[]){
for(int i=M-1;i>=0;i--){
if(a[i]>b[i]){
memcpy(c,a,sizeof ss);
return ;
}
if(a[i]<b[i]){
memcpy(c,b,sizeof ss);
return ;
}
}
memcpy(c,b,sizeof ss);
return ;
}
void out(int c[]){
int k=M-1; bool flag=0;
while(k>=1&&!c[k])k--;
for(int i=k;i>=0;i--){
if(!flag)printf("%d",c[k]),flag=1;
else printf("%08d",c[i]);
}
cout<<endl;
}
int qmi2[N][M];
int a[N][N];
int main(){
scanf("%d%d",&n,&m);
qmi2[0][0]=1;
for(int i=1;i<=m;i++)mul(qmi2[i],qmi2[i-1],2);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
}
}
int ans[M]={0};
for(int i=1;i<=n;i++){
memset(f,0,sizeof f);
for(int len=1;len<=m;len++){
for(int l=1;l+len-1<=m;l++){
if(len==1){
mul(f[l][l],qmi2[m],a[i][l]);
continue;
}
int r=l+len-1;
int p=m-(r-l+1)+1;
int temp[M];
mul(temp,qmi2[p],a[i][r]);
add(temp,f[l][r-1],temp);
maxv(f[l][r],f[l][r],temp);
mul(temp,qmi2[p],a[i][l]);
add(temp,f[l+1][r],temp);
maxv(f[l][r],f[l][r],temp);
}
}
add(ans,ans,f[1][m]);
}
out(ans);
}