题目描述：
有一个由1到9的n个数字的数字串，问如果将m个加号插入到这个数字中，在各种可能中形成的表达式中，最小的那个表达式的值是多少？
思路：添加完加号后，表达式最后一个加号在最后的第i个数字后面，表达式最小值等于前面m-1个加号所能形成的最小值加上i+1到最后那个数字所组成的数的值
代码如下：
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; int dp[100][200]; char str[500]; //dp[m][n]表示的是示在n个数字中插入m个加号所能形成的表达式最小值 int change(int x,int y) { int t=0; for(int i = x ; i <= y ; i++) { t*=10; t+=(str[i]-'0'); } return t; } int main() { int n,m; while(scanf("%d%d",&m,&n)!=EOF) { scanf("%s",str+1); memset(dp,999999,sizeof(dp)); for(int i = 1 ; i <= n ; i++) dp[0][i]=change(1,i); for(int i = 1 ; i <= m ; i++) for(int j = i ; j <= n ; j++) for(int k = i ; k <= j ; k++) dp[i][j]=min(dp[i][j],dp[i-1][k]+change(k+1,j)); printf("%d\n",dp[m][n]); } return 0; }