P1018 题目 记录

第一个测试点数据：

6 2

356510

输出：107100

本地过了，洛谷没过，肥肠奇怪

#include<bits/stdc++.h>
using namespace std;
const int K = 10;
const int N = 50;
const int LEN = 1000;
int n,kk,mp[N][N][LEN];
int dp[N][K][LEN];
int ret[LEN],re[LEN];
char c;
void qread(int *x){
	*x = 0;
	c = getchar();
	while(c<'0'||c>'9'){
		c = getchar();
	}
	while(c>='0'&&c<='9'){
		*x = *x*10+c-'0';
		c=getchar();
	}
}
void empty(int *x){
	if(!x[0]){
		x[0] = 1;
		return;
	}
	for(int i = 1;i <= x[0];i++){
		x[i] = 0;
	}
	x[0] = 1;
}
void copy(int *x,int *y){
	for(int i = 0;i <= y[0];i++){
		x[i] = y[i];
	}
}
void print(int *x){
	for(int i = x[0];i>=1;i--){
		printf("%c",x[i]+'0');
	}
//	printf("\n");
}
int* bijiao(int *x,int *y){
	if(x[0]>y[0]){
		return x;
	}
	else if(x[0]<y[0]){
		return y;
	}
	else{
		for(int i = x[0];i >= 1;i--){
			if(x[i]>y[i]){
				return x;
			}
			if(x[i]<y[i]){
				return y;
			}
		}
	}
}
int* add(int *x,int *y){//高精加法
	empty(ret);
	for(int i = 1;i <= max(x[0],y[0]);i++){
		ret[i] = x[i]+y[i];
	}
	for(int i = 1;i <= max(x[0],y[0])||ret[i];i++){
		ret[i+1]+=ret[i]/10;
		ret[i]=ret[i]%10;
		ret[0] = i;
	}
	return ret;
}
int* cheng(int *x,int b){//高精乘低精
	empty(re);
	for(int i = 1;i <= x[0];i++){
		re[i] = x[i]*b;
	}
	for(int i = 1;i <= x[0]||re[i];i++){
		re[i+1]+=re[i]/10;
		re[i]=re[i]%10;
		re[0] = i;
	}
	return re;
}

int* mul(int *x,int *y){//高精乘高精
	empty(re);
	for(int i = 1;i <= x[0];i++){
		for(int j = 1;j <= y[0];j++){
			re[i+j-1] += x[i]*y[j];
		}
	}
	for(int i = 1;i <= x[0]+y[0]-1||re[i];i++){
		re[i+1]+=re[i]/10;
		re[i]=re[i]%10;
		re[0] = i;
	}
	return re;
}
int main(){
	qread(&n);
	qread(&kk);
	for(int i = 1;i <= n;i++){
		mp[i][i][0]=1;
		mp[i][i][1]=getchar()-'0';
	}
	for(int i = 1;i <= n;i++){
		for(int j = i+1;j <= n;j++){
			copy(mp[i][j],add(cheng(mp[i][j-1],10),mp[j][j]));
		}
	}
	for(int i = 1;i <= n;i++){
		copy(dp[i][0],mp[1][i]);
	}
	for(int i = 2;i <= n;i++){
		for(int k = 1;k < i&&k<=kk;k++){
			for(int j = k;j < i;j++){
				copy(dp[i][k],bijiao(dp[i][k],mul(dp[j][k-1],mp[j+1][i])));
	//			print(dp[j][k-1]);
	//			print(mp[j+1][i]);
	//			print(dp[i][k]);
	//			printf("%d %d %d-------------------\n",k,i,j);
			}
		}
	}
	print(dp[n][kk]);
	return 0;
}

求大佬帮调