题目描述

当Alice在浏览数学书时，看到一个等式A=S，奇怪的是A和S并不相等。Alice发现可以通过在A中添加加号“+”从而使得等式成立。 
　　编程计算最少需要插入多少加号使得等式成立。允许每个数有多个前导0

思路

设f[i][j]为前i个数和为j时的最少加号个数

#include <string>
#include <cstring>
#include <stdio.h>
using namespace std;
#define N 1001
#define max(x, y) ((x) > (y) ? (x) : (y))
#define min(x, y) ((x) < (y) ? (x) : (y))
#define fill(x, y) memset(x, y, sizeof(x))
#define INF 0x7f7f7f7f
int a[N], f[N][5011];
inline int read()
{
    int x = 0; char ch = getchar();
    while (ch < '0' || ch > '9') {ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + ch - '0'; ch = getchar();}
    return x;
}
int getnum(int l, int r)
{
    int t = 0;
    for (int i = l; i <= r; i++)
        t = t * 10 + a[i];
    return t;
}
int main()
{
    int n = 0;
    char ch = getchar();
    while (ch != '=') 
    {
        a[++n] = ch - '0';
        ch = getchar();
    }
    int m = read();
    fill(f, INF);
    f[0][0] = -1;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
            for (int k = max(i - 3, 1); k <= i; k++)
            {
                int num = getnum(k, i);
                if (j >= num) f[i][j] = min(f[i][j], f[k - 1][j - num] + 1);
            }
    printf("%d\n", f[n][m]);
}