社区讨论

求dalao指教

P1005[NOIP 2007 提高组] 矩阵取数游戏参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lo117il1
此快照首次捕获于
2023/10/22 13:31
2 年前
此快照最后确认于
2023/11/02 13:03
2 年前
查看原帖
10分代码,高精度没啥问题用很多次了 动规代码哪里错了qwq
CPP
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

struct lon{
	int l;
	char x[101];
	
	lon(){
		memset(this,0,sizeof(lon));
		l=1;
	}
	
	void in(){
		char t;
		l=0;
		do{
			t=getchar();
		}while(t<'0'||t>'9');
		while(t>='0'&&t<='9'){
			l++;
			x[l]=t-'0';
			t=getchar();
		}
		for(int i=1;i<=l>>1;i++){
			swap(x[i],x[l-i+1]);
		}
		return ;
	}
	
	void out(){
		for(int i=l;i>=1;i--){
			printf("%d",x[i]);
		}
		return ;
	}
};

lon maxof(lon x,lon y){
	for(int i=max(x.l,y.l);i>=1;i--){
		if(x.x[i]>y.x[i])return x;
		if(x.x[i]<y.x[i])return y;
	}
	return x;
}

lon add(lon x,lon y){
	lon ans;
	int l=ans.l=max(x.l,y.l);
	for(int i=1;i<=l;i++){
		ans.x[i]+=x.x[i]+y.x[i];
		ans.x[i+1]+=ans.x[i]/10;
		ans.x[i]%=10;
	}
	if(ans.x[l+1])ans.l++;
	return ans;
}

lon mult(lon x,lon y){
	lon ans;
	ans.l=x.l+y.l-1;
	for(int i=1;i<=x.l;i++){
		for(int j=1;j<=y.l;j++){
			ans.x[i+j-1]+=x.x[i]*y.x[j];
			ans.x[i+j]+=ans.x[i+j-1]/10;
			ans.x[i+j-1]%=10;
		}
	}
	while(ans.x[ans.l+1]){
		ans.l++;
	}
	return ans;
}

lon con[81];

int n,m;
lon ans;



void find(){
	lon arr[81];
	lon dp[81][81];
	
	for(int i=1;i<=m;i++)
		arr[i].in();
	
	for(int i=1;i<m;i++){
		for(int j=m;j>i;j--){
			dp[i+1][j]=maxof(dp[i+1][j],add(dp[i][j],mult(con[i+m-j+1],arr[i])));
			dp[i][j-1]=maxof(dp[i][j-1],add(dp[i][j],mult(con[i+m-j+1],arr[j])));
		}
	}
	
	lon tmp;
	for(int i=1;i<=m;i++){
		tmp=maxof(tmp,dp[i][i]);
	}
	
	ans=add(ans,tmp);
//	tmp.out();
//	printf("\n");
	return ;
}

int main(){
	scanf("%d%d",&n,&m);
	
	con[1].x[1]=2;
	for(int i=2;i<=m+1;i++)
		con[i]=mult(con[i-1],con[1]);
	
	for(int i=1;i<=n;i++)
		find();
	
	ans.out();
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...