求助,为什么WA了?
查看原帖
求助,为什么WA了?
141577
yhc12345楼主2020/12/4 20:00
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=90,M=50;
int n,m;
struct bign {
	int val[M],dig;
	bign() {
		memset(val,0,sizeof(val));
		dig=1;
	}
};
bign dp[N][N],ans;
int a[N][N];
int p[N];
bign operator *(bign a,int b) {
	bign c;
	c.val[1]=a.val[1]*b;
	c.dig=a.dig+1;
	for(int i=1;i<c.dig;i++) {
		c.val[i+1]+=c.val[i]/10;
		c.val[i]%=10;
	}
	while(c.dig>1&&c.val[c.dig]==0) {
		c.dig--;
	}
	return c;
}
bign operator +(bign a,bign b) {
	bign c;
	c.dig=max(a.dig,b.dig)+1;
	for(int i=1;i<=c.dig;i++) {
		c.val[i]=a.val[i]+b.val[i];
	}
	for(int i=1;i<c.dig;i++) {
		c.val[i+1]+=c.val[i]/10;
		c.val[i]%=10;
	}
	if(c.val[c.dig]==0) {
		c.dig--;
	}
	return c;
}
bign pow(int k) {
	bign c;
	c.val[1]=1;
	for(int i=1;i<=k;i++) {
		for(int j=1;j<=c.dig;j++) {
			c.val[j]*=2;
		}
		for(int j=1;j<=c.dig;j++) {
			c.val[j+1]+=c.val[j]/10;
			c.val[j]%=10;
		}
		if(c.val[c.dig+1]>0) {
			c.dig++;
		}
	}
	return c;
}
bign max(bign a,bign b) {
	if(a.dig!=b.dig) {
		return a.dig>b.dig?a:b;
	}
	bool flag=true;
	for(int i=a.dig;i>=1;i--) {
		if(a.val[i]<b.val[i]) {
			flag=false;
			break;
		}
		else if(a.val[i]>b.val[i]) {
			break;
		}
	}
	return flag?a:b;
}
int main() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			scanf("%d",&a[i][j]);
		}
	}
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) {
			for(int k=1;k<=m;k++) {
				dp[j][k]=bign();
			}
		}
		for(int l=m-1;l>=1;l--) {
			for(int j=1;j+l-1<=m;j++) {
				int r=j+l-1,c=m-l;
				dp[j][r]=max(dp[j-1][r]+pow(c)*a[i][j-1],dp[j][r+1]+pow(c)*a[i][r+1]);
			}
		}
		bign mx;
		for(int j=1;j<=m;j++) {
			mx=max(mx,dp[j][j]+pow(m)*a[i][j]);
		}
		ans=ans+mx;
	}
	for(int i=ans.dig;i>=1;i--) {
		printf("%d",ans.val[i]);
	}
}
2020/12/4 20:00
加载中...