P1018 [NOIP2000 提高组] 乘积最大-dp 高精度

---

题目链接

---

思路：

显然dp能写，但是要找到状态转移方程是核心，于是我开始手动模拟寻找答案的过程，加入数据是 1 2 3 4 5 插入两个乘号，我们知道如果不插入乘号这这个最大值就是它自己，当插入一个乘号的时候，这个乘号只能从至少2个数开始插入同时我们知道一个乘号会把数字分成前后两段，但是具体要放在哪里这是需要枚举的比如我们寻找前5个数插入1个乘号时的最大值，则枚举过程为前2个数不插入乘号时的最大值乘以后三个数，前3个数不插入乘号时乘以后2个数，前4个数不插入乘号时乘以后面一个数。至此dp的状态转移方程以及dp如何构造已经十分清楚了。我们令dp[i][j]代表在前j个数插入i个乘号的最大值。同时状态转移方程为dp[i][j]=max(dp[i][j],dp[i-1][z][z+1,j]),i-1<z<j
因为题目涉及高精度，所以定义为dp[i][j][100]。其他的就是一些比如高精乘以及高精度之间的比较函数之类的基础方法了，细心即可，接下来放ac代码。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int n,k,arr[50];
char str[50];
int dp[7][50][100];
int min(int a,int b){
	if(a<b)return a;
	else return b;
}
int *mult(int *a,int l,int r){//返回a与[l,r]的乘积 
	int *b=(int *)malloc(100*sizeof(int));//动态分配 
	memset(b,0,sizeof(int)*100);
	int remain[100]={0};
	for(int i=r;i>=l;i--){
		remain[++remain[0]]=arr[i];
	}
	for(int i=1;i<=remain[0];i++){//高精乘法 
		int w=0;
		for(int j=1;j<=a[0];j++){
			b[j+i-1]=remain[i]*a[j]+b[j+i-1]+w;
			w=b[j+i-1]/10;
			b[j+i-1]%=10;
		}
		b[0]=a[0]+i-1;
		while(w){
			b[++b[0]]=w%10;
			w/=10;
		}
	}
	return b;
}
int cmp(int *a,int *b){//比较函数 
	if(a[0]>b[0])return 1;
	if(a[0]<b[0])return -1;
	for(int i=a[0];i>0;i--){
		if(a[i]>b[i])return 1;
		if(a[i]<b[i])return -1;
	}
	return 0;
}
int main(){
	scanf("%d%d",&n,&k);
	scanf("%s",str+1);
	arr[0]=strlen(str+1);
	for(int i=1;i<=arr[0];i++){
		arr[i]=str[i]-'0';
	}
	for(int i=1;i<=arr[0];i++){
		for(int j=i;j>0;j--){
			dp[0][i][++dp[0][i][0]]=arr[j];
		}
	}
	for(int i=1;i<=min(k,n-1);i++){
		for(int j=i+1;j<=n;j++){
			for(int z=i;z<j;z++){
				int *c=mult(dp[i-1][z],z+1,j);
				int judge=cmp(dp[i][j],c);
				if(judge==-1){
					memcpy(dp[i][j],c,sizeof(int)*(c[0]+3));
				} 
				free(c);
			}
		}
	}
	for(int i=dp[k][n][0];i>0;i--){
		printf("%d",dp[k][n][i]);
	}
	return 0;
}