入门OJ 3791: [Noip模拟题]快速求和
题目
Description
给定一个数字字符串，用最少次数的加法让字符串等于一个给定的目标数字。每次加法就是在字符串的某个位置插入一个加号。在需要的所有加号都插入后，就象做普通加法那样来求值。例如，考虑字符串"12"，做0次加法，我们得到数字12。如果插入1个加号，我们得到3。因此，这个例子中，最少用1次加法就得到数字3。再举一例，考虑字符串"303"和目标数字6，最佳方法不是3+0+3，而是3+03。能这样做是因为1个数的前导0不会改变它的大小。写一个程序来实现这个算法。
Input
第1行：1个字符串S(1 ≤ S的长度 ≤ 40)
和1个整数N(N≤100000)。S和N用1个空格分隔。
## Output
第1行：1个整数K，表示最少的加法次数让S等于N。如果怎么做都不能让S等于N，则输出-1。
# 题解 做法：DP
首先因为S长度不大，我们可以定义一个数组sum[i][j]来存从i开始以j为结束对应的字符串所表示的数，时间复杂度
\(\Theta({(strlen(S))}^{2})\)
定义dp[i][j]表示前i个数字组成j所需要的最少+数，不难得到
1
f[i][k+g[j+1][i]]=min(f[i][k+g[j+1][i]],f[j][k]+1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
using namespace std;
const int kMaxInt(2147483647);
int dp[50][100010], sum[50][50], target, length;
string str;
int main(int argc, char **argv) {
cin >> str >> target;
length = str.length();
for (register int i(0); i <= length; ++i) {
for (register int j(0); j <= target; ++j) {
dp[i][j] = kMaxInt;
}
}
for (register int i(1); i <= length; ++i) {
sum[i][i] = str[i - 1] - '0';
}
for (register int i(1); i < length; ++i) {
for (register int j(i + 1); j <= length; ++j) {
sum[i][j] = sum[i][j - 1] * 10 + sum[j][j];
if (j - i > 9) sum[i][j] = kMaxInt;
}
}
dp[0][0] = -1;
for (register int i(1); i <= length; ++i) {
for (register int j(1); j <= i; ++j) {
if (sum[i - j + 1][i] > target) break;
for (register int k(0); k <= target; ++k) {
if (dp[i - j][k] != kMaxInt) {
if (k + sum[i - j + 1][i] > target) break;
//这一步相当于剪枝，因为这道题本来也可以暴搜+剪枝
dp[i][k + sum[i - j + 1][i]] = min(dp[i][k + sum[i - j + 1][i]],
dp[i - j][k] + 1);
}
}
}
}
if (dp[length][target] == kMaxInt) puts("-1");
else cout << dp[length][target] <<endl;
return 0;
}