高精出锅了
查看原帖
高精出锅了
216438
Dreamsuzki楼主2020/11/26 21:08
#include <bits/stdc++.h>

using namespace std;
const int N=50;

struct bigint{
    int len,num[N];
	bigint() {
		memset(num,0,sizeof num);
		len=0;
	}
    void read() {
        string s;
        cin>>s;
        len=s.size();
        for(int i=0; i<len; i++) num[i]=s[len-i-1]-'0';
    }
    void print() {
        for(int i=len-1; i>=0; i--) cout<<num[i];
    }
    bool operator <= (const bigint &b)const {
        if(len<b.len) return true;
        if(len>b.len) return false;
        for(int i=len-1; i>=0; i--)
            if(num[i]!=b.num[i])
                return num[i]<b.num[i];
        return true;
    }
    bigint operator + (const bigint &b)const {
        bigint result;
        int G[N]={},len_ans=max(len,b.len);
        for(int i=0; i<=len_ans; i++) {
            result.num[i]=num[i]+b.num[i]+G[i];
            if(result.num[i]>=10) {
                result.num[i]-=10;
                G[i+1]=1;
            }
        }
        if(result.num[len_ans]==0) result.len=len_ans;
        else result.len=len_ans+1;
        return result;
    }
    bigint operator - (const bigint &b)const {
        bigint result;
        int W[N]={},len_ans=max(len,b.len);
        for(int i=0; i<len_ans; i++) {
            result.num[i]=num[i]-b.num[i]-W[i];
            while(result.num[i]<0) {
                result.num[i]+=10;
                W[i+1]=1;
            }
        }
        while(len_ans>=2 && result.num[len_ans-1]==0) len_ans--;
        result.len=len_ans;
        return result;
    }
    bigint operator * (const bigint &b)const {
        bigint result;
        memset(result.num,0,sizeof result.num);
        int len_ans=len+b.len+1;
        for(int i=0; i<len; i++)
            for(int j=0; j<b.len; j++)
                result.num[i+j]+=(num[i]*b.num[j]);
        for(int i=0; i<len_ans; i++) {
            result.num[i+1]+=(result.num[i])/10;
            result.num[i]%=10;
        }
        while(len_ans>=2 && result.num[len_ans-1]==0) len_ans--;
        result.len=len_ans;
        return result;
    }
    bigint operator / (const bigint &b)const {
        bigint XR,result;
        XR.len=0;
        memset(result.num,0,sizeof result.num);
        for(int i=len-1; i>=0; i--) {
            for(int j=XR.len-1; j>=0; j--) XR.num[j+1]=XR.num[j];
            XR.num[0]=num[i];
            if(XR.num[XR.len]!=0) XR.len++;
            while(b<=XR) {
                XR=XR-b;
                result.num[i]++;
            }
        }
        int len_ans=len;
        while(len_ans>=2 && result.num[len_ans-1]==0) len_ans--;
        result.len=len_ans;
        return result;
    }
};

int n,m;
bigint f[100][100],power[100],ans,val[100];

bigint max(bigint a,bigint b) {
	if(a<=b) return b;
	return a;
}

int main() {
	scanf("%d%d",&n,&m);
	power[0].len=1;power[0].num[0]=1;
	bigint tmp;tmp.len=1;tmp.num[0]=2;
	for(int i=1; i<=100; i++) power[i]=tmp*power[i-1];
	while(n--) {
		for(int i=1; i<=m; i++) val[i].read();
		memset(f,0,sizeof f);
		for(int i=1; i<=m; i++)
		    for(int j=m; j>=i; j--) {
		    	f[i][j]=max(f[i][j],f[i-1][j]+power[m-(j-i+1)]*val[i-1]);
		    	f[i][j]=max(f[i][j],f[i][j+1]+power[m-(j-i+1)]*val[j+1]);
			}
		bigint maxx;
		for(int i=1; i<=m; i++) maxx=max(maxx,f[i][i]+power[m]*val[i]);
		ans=ans+maxx;
	}
	ans.print();
	return 0;
}

我人都调傻了,把高精换int答案是对的,所以应该是高精的锅。

样例都没过。

2020/11/26 21:08
加载中...