题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=746
题目大意：给出两个整数 n , m ,要求在 n 中加入m - 1 个乘号，将n分成m段，求出这m段的最大乘积
具体思路：首先用一个数组a[i][j]表示这个字符串从第i个位置到第j个位置的数是多大的，然后就开始DP就可以了。
dp[i][j]代表从第0到第i个位置，分成j段的最大价值。
dp[i][j]=max(dp[i][j],dp[k][j-1]*a[k+1][i])。
伪AC代码：（网站崩了，没法测题）
1 #include<iostream> 2 #include<stdio.h> 3 #include<cstring> 4 using namespace std; 5 # define ll long long 6 # define inf 0x3f3f3f3f 7 const int maxn = 4+100; 8 const int mod =1e6; 9 # define LL_inf 0x3f3f3f3f3f3f3f 10 char str[maxn]; 11 int a[maxn][maxn]; 12 int dp[maxn][maxn]; 13 int main(){ 14 int T; 15 scanf("%d",&T); 16 while(T--){ 17 memset(a,0,sizeof(a)); 18 memset(dp,0,sizeof(dp)); 19 scanf("%s",str); 20 int m; 21 scanf("%d",&m); 22 int len=strlen(str); 23 for(int i=0;i<len;i++){ 24 a[i][i]=str[i]-'0'; 25 for(int j=i+1;j<len;j++){ 26 a[i][j]=a[i][j-1]*10+str[j]-'0'; 27 } 28 } 29 for(int i=0;i<len;i++){ 30 dp[i][1]=a[0][i]; 31 for(int j=2;j<=m;j++){ 32 for(int k=0;k<i;k++){ 33 dp[i][j]=max(dp[i][j],dp[k][j-1]*a[k+1][i]); 34 } 35 } 36 } 37 printf("%d ",dp[len-1][m]); 38 } 39 return 0; 40 }