快速求和

【动态规划2】线性状态动态规划：P1874 快速求和

题目描述

给定一个数字字符串，用最小次数的加法让字符串等于一个给定的目标数字。每次加法就是在字符串的某个位置插入一个加号。在里面要的所有加号都插入后，就像做普通加法那样来求值。

例如，考虑字符串12，做 $0$ 次加法，我们得到数字 $12$。如果插入 $1$ 个加号，我们得到 $3$，因此，这个例子中，最少用 $1$ 次加法就得到数字 $3$。

再举一例，考虑字符串303和目标数字 $6$，最佳方法不是3+0+3。而是3+03。能这样做是因为一个数的前导 $0$ 不会改变它的大小。

输入格式

第一行：一个字符串 $s$。

第二行：一个整数 $n$。

输出格式

一行一个整数表示最少的加法次数让 $s$ 等于 $n$。如果怎么做都不能让 $s$ 等于 $n$ ，则输出 $-1$。

样例 #1

样例输入 #1

1
2
99999
45

样例输出 #1

1
4

提示

数据规模与约定

对于 $100%$ 的数据，保证 $1\le \operatorname{len}(s)\le40$，$1 \leq n\le10^5$。

解题思路

image-20240219152721796

需要注意，我们这个字符串的长度是大于long的范围的，但是我们根据题意，大于n的数字都用不着。所以大于n我们直接返回最大值就好

代码

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
41
42
43
44
45
46
47
import java.io.*;
import java.util.*;

class Main{
    public static int N = 50,M = 100010,n;
    public static int[][] dp = new int[N][M];
    public static Scanner sc = new Scanner(System.in);

    public static int getDigit(String s, int l, int r){
        String subString = s.substring(l-1,r);

        int res = 0;
        for(int i = 0;i < subString.length();i++){
            res = res * 10 + subString.charAt(i) - '0';
            if(res > n) return 0x3f3f3f3f;
        }
        return res;
    }


    public static void main(String[] args)throws Exception{
        String s = sc.next();
        n = sc.nextInt();

        //初始化
        for(int i = 0;i <= s.length();i++){
            Arrays.fill(dp[i],0x3f3f3f3f);
            if(i == 0 || getDigit(s,1,i) >= n) continue;
            dp[i][getDigit(s,1,i)] = 0;
        }


        for(int i = 1;i <= s.length();i++){
            for(int j = 1;j <= n;j++){
                for(int k = 1;k < i;k++){
                    if(j - getDigit(s,k+1,i) >= 0)
                        dp[i][j] = Math.min(dp[i][j],dp[k][j - getDigit(s,k+1,i)] + 1);
                }
            }
        }

        int res = 0;
        if(dp[s.length()][n] == 0x3f3f3f3f) res = -1;
        else res = dp[s.length()][n];
        System.out.println(res);
    }
}