洛谷题单指南-动态规划2-P1874 快速求和

原题链接：https://www.luogu.com.cn/problem/P1874

题意解读：一个数字字符串s，分解成几个整数，和为n，计算最少加号个数，也就是计算最少分解的整数个数-1。

解题思路：此题虽然分类在动态规划，但数据量不大，DFS更加直观和易于理解，所以采用DFS暴搜+剪枝来解决。

搜索思路是对数字字符串依次枚举前1/2/3/4...个数字组成整数，直到整数超过目标和，然后递归处理字符串剩下的部分，同时目标和减去前面的整数。

要想不超时，需要进行合理的剪枝：

剪枝1：当枚举到字符串前面的整数是0，且不是最后一位时，没必要继续往下递归，这样的拆分是多余的，要去除前导0，继续往后枚举

剪枝2：当枚举到字符串前面的整数大于目标和，没必要再枚举下去，直接退出循环

剪枝3：当枚举到字符串前面的整数后，剩下部分的整数如果比剩下的目标和小，那么继续讲剩下的字符串拆分之后的和会越来越小，没必要再枚举下去，退出循环

100分代码：

#include <bits/stdc++.h>
using namespace std;

string s;
int n;
int ans = INT_MAX;

//从字符串s的start开始，挑选出若干整数之和等于sum，cnt记录有多少个整数
void dfs(int start, int sum, int cnt)
{
    if(start == s.size() && sum == 0)
    {
        ans = min(ans, cnt - 1); //加号数量是整数数量-1
        //cout << cnt - 1 << endl;
        return;
    }
    int num = 0;
    for(int i = start; i < s.size(); i++)
    {
        num = 10 * num + s[i] - '0'; //枚举前0~i数字组成的整数
        if(num == 0 && i < s.size() - 1) continue; //剪枝1：整数的前导0没必要单独抽取出来，最后的0需要单独抽取出来
        if(num > sum) break; //剪枝2：如果整数超过sum，结束，因为再往后num更大
        if( s.size() - i <= 15)
        {
            long long remain = 0;
            for(int j = i; j < s.size(); j++)
            {
                remain = 10 * remain + s[j] - '0';
            }
            if(remain < sum - num) break; //剪枝3：如果字符串剩下部分的整数比sum-num还小，后续的划分只会越来越小，可以结束
        }
        dfs(i + 1, sum - num, cnt + 1); //前0~i个数字划为一个整数，继续处理后面的数字，'+'加1
    }
}

int main()
{
    cin >> s >> n;
    dfs(0, n, 0);
    if(ans == INT_MAX) cout << -1;
    else cout << ans;
    return 0;
}