题意：给定一个长度为n的数字串，求在其中插入k个乘号的最大乘积
N,K（6≤N≤40,1≤K≤6，6≤N≤40,1≤K≤6）
很水的区间dp，设dp[i][j]表示在前i位插入j个乘号的最大乘积。
则有初始状态：
dp[i][0]=submit(1,i); (submit(l,r)表示原数字串从l到r的字串)
考虑枚举最后一个乘号的位置，则有转移方程：
第j个乘号在这
然后就是一个高精度的问题了。
然而我在两个数组的比较上打错了
bool ifmax(int a[],int b[]) { int l1=a[0],l2=b[0]; if(l1>l2) return true; if(l1<l2) return false; for(int i=l1;i>=1;i--) if(a[i]>b[i]) return true; else return false; return false; }这是我原来的打法，在a[i]==b[i]时我也return false 了，就是一个很小的问题，然而我调了几个小时。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define MAXN 100 #define MAXM 10 using namespace std; int n,m; char s[MAXN]; int f[MAXN][MAXN][MAXN]; void cut(int a[],int l,int r) { int k=0; for(int i=r-1;i>=l-1;i--) { k++; a[k]=s[i]-'0'; } a[0]=k; } void multiply(int ans[],int a[],int b[]) { int l1=a[0]; int l2=b[0]; for(int i=1;i<=l1;i++) for(int j=1;j<=l2;j++) { ans[i+j-1]+=a[i]*b[j]; } for(int i=1;i<=l1+l2-1;i++) { if(ans[i]>=10) { ans[i+1]+=ans[i]/10; ans[i]%=10; } } ans[0]=l1+l2; while(ans[ans[0]]==0&&ans[0]>1) ans[0]--; } bool ifmax(int a[],int b[]) { int l1=a[0],l2=b[0]; if(l1>l2) return true; if(l1<l2) return false; for(int i=l1;i>=1;i--) if(a[i]>b[i]) return true; else if(a[i]<b[i])return false; return false; } int main() { cin>>n>>m; cin>>s; for(int i=0;i<MAXN;i++) { for(int j=0;j<MAXN;j++) f[i][j][0]=1; } for(int i=1;i<=n;i++) { cut(f[i][0],1,i); } for(int i=2;i<=n;i++) for(int j=1;j<=min(m,i-1);j++) for(int k=j;k<i;k++) { int ans[MAXN]={0}; int a[MAXN]={0}; cut(a,k+1,i); multiply(ans,f[k][j-1],a); if(ifmax(ans,f[i][j])) { for(int ii=1;ii<=ans[0];ii++) f[i][j][ii]=ans[ii]; f[i][j][0]=ans[0]; } } for(int i=f[n][m][0];i>=1;i--) cout<<f[n][m][i]; }
