P1874 快速求和

题目

P1874 快速求和

算法标签: 动态规划, 线性$dp$

思路

求的是最少组成$n$的加法次数, 对于当前数字序列可以设计状态表示$f[i][j]$表示考虑前$i$个字符, 并且和是$j$的所有方案中加法次数最小的方案, 那么就要考虑状态转移, 按照最后一步的思想, 可以将集合划分为最后一个数字的长度, 也就是最后一个数字是什么, 算法时间复杂度$O(n\times len)$

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;
const LL INF = 5e18, N = 55, M = 1e5 + 40;

string s;
LL w[N], nums[N][N], cnt;
LL sum, n, f[N][M];
bool vis;

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> s >> sum;
    n = s.size();

    //去除前导0
    for (int i = 0; s[i]; ++i) {
   
        if (s[i] != '0') vis = true;
        if (vis) w[++cnt] = s[i] - '0';
    }
    if (cnt == 0) w[++cnt] = 0;

    //预处理两个位置直接组成的数字大小
    for (int i = 1; i <= cnt; ++i) {
   
        nums[i][i] = w[i];
        for (int j = i; j - i <= 11 && j <= cnt; ++j) {
   
            nums[i][j] = nums[i][j - 1] * 10 + w[j];
        }
    }

    //初始化dp
    for (int i = 0; i <= cnt + 1; ++i) {
   
        for (int j = 0; j <= sum + 1; ++j) f[i][j] = INF;
    }

    f[0][0] = 0;
    for (int i = 1; i <= cnt; ++i) {
   
        //枚举最后一个数字的大小
        for (int k = 1; k <= 11; ++k) {
   
            if (i >= k) {
   
                LL curr = nums[i - k + 1][i];
                for (LL j = curr; j <= sum; ++j) {
   
                    f[i][j] = min(f[i][j], f[i - k][j - curr] + 1);
                }
            }
        }
    }

    int ans;
    if (f[cnt][sum] > cnt) ans = -1;
    else ans = f[cnt][sum] - 1;

    cout << ans << "\n";
    return 0;
}