最佳加法表达式 [dp]

#include <iostream>
#include <string>
#include <math.h>
#include<algorithm>
using namespace std;
const int maxn = 1010;

int a[maxn], num[maxn][maxn], dp[maxn][maxn];//num[u][v]代表u到v位的数字

int main()
{
	int n, m;
	while (cin >> n >> m)
	{
		for (int i = 1; i <= n; i++)
		{
			cin >> a[i];
		}
		for (int i = 1; i <= n; i++)
		{
			num[i][i] = a[i];
			for (int j = i + 1; j <= n; j++)
			{
				num[i][j] = num[i][j - 1] * 10 + a[j];
			}
		}
		memset(dp, 0x3f, sizeof(dp));
		for (int i = 1; i <= n; i++)
		{
			dp[0][i] = num[1][i];
		}
	/*	for (int i = 1; i <= m; i++)
			for (int j = 1; j <= n; j++)
				if (i + 1 > j)
					dp[i][j] = inf;*/
		for (int i = 1; i <= m; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				for (int k = i; k <= j; k++)
				{//i-1个加号放到k个数中
					dp[i][j] = min(dp[i][j], dp[i - 1][k] + num[k + 1][j]);
				}
			}
		}
		cout << dp[m][n] << endl;
	}
}