问题描述
有一个由1......9组成的数字串,问:如果将m个加号插入到这个数字串中,在各种可能形成的表达式中,值最小的那个表达式的值是多少?
解题思路
假定数字串长度是n,添完加号后,表达式的最后一个加号添加在第i个数字的后面,那么整个表达式的最小值,就等于在前i个数字中插入m-1个加号所能形成的最小值,再加上第i+1到第n个数字所组成的数的值(i从1开始算)。
设V(m,n)表示在n个数字中插入m个加号所能形成的表达式最小值,那么:
if m = 0
V(m,n) = n个数字构成的整数
else if n < m + 1
V(m,n) = ∞
else
V(m,n) = Min{ V(m-1,i) + Num(i+1,n) } ( i = m … n-1 )
Num(i,j)表示从第i个数字到第j个数字所组成的数。数字编号从1开始算。此操作时间复杂度是O(j-i+1),总时间复杂度是O(mn2)。
程序实现
#include<iostream>
#include<string>
#include<cstdlib>
#include<cstdio>
using namespace std;
const int MAXN = 1001;
const int MAXM = 1001;
const int INFINITE = 1000000;
int f[MAXN][MAXM];
int main()
{
string str;
cin >> str;
int m;
cin >> m;
int n = str.length();
str = "0" + str;
for(int i = 0; i <= n; i++)
for(int j = 0; j <= m; j++)
f[i][j] = INFINITE;
for(int i = 1; i <= n; i++)
{
for(int j = 0; j <= m; j++)
{
if(j == 0)
{
f[i][j] = atoi(str.substr(1, i).c_str());
cout << "i=" << i << "," << "j=" << j << "," << f[i][j] << endl;
continue;
}
if(i == j + 1)
{
int tmp = 0;
for(int s = 1; s <= i; s++)
tmp += str[s] - '0';
f[i][j] = tmp;
cout << "i=" << i << "," << "j=" << j << "," << f[i][j] << endl;
}
if(i > j + 1)
{
for(int k = j; k <= i - 1; k++)
{
int num = atoi(str.substr(k + 1, i - k).c_str());
f[i][j] = min(f[i][j], f[k][j - 1] + num);
cout << "i=" << i << "," << "j=" << j << "," << "num=" << num << "," << f[i][j] << endl;
}
}
}
}
if(f[n][m] < INFINITE) cout << f[n][m] << endl;
else cout << "None!" << endl;
}
网友评论