[Leaf] P1874 快速求和

p1874-快速求和---洛谷">P1874 快速求和 - 洛谷

1. 题面梗概

中译中：给一个长字符串，在中间切 $k$ 刀变成若干个数，求最少切几刀能让这些数加起来等于 $n$。

$1 \leq len(s) \leq 40, 1 \leq n \leq 10^5$

2. 逻辑推导

这是一道同时具有 “子段划分” 和 “背包” 两个模型的题，既要考虑把原串划分为若干个段，又要让它们的和等于目标数字。

2.1 状态

因为不需要区分段的个数，只要最小化它，所以状态记录的是某个局面的最少加号。

记 $f[i][k]$ 为只使用字符串前 $i$ 位，数字和为 $k$ 的最少操作数。

接着考虑 $f[i][k]$ 的前继，就只需要知道具体的 “最后一段”，那么枚举这个 “最后一段” 的起点就行了。

$$f[i][k] = \min_{j < i}(f[j][k - val(j + 1, i)]) + 1$$

$val(j + 1, i)$ 表示 $S[j + 1, \dots, i]$ 对应的数字值。

这个方程的含义是：把字符串的 $j + 1 \to i$ 这一段拎出来，接在某个以 $j$ 记为的数字和为 $k - val( j + 1, i )$ 的串上，就可以拼出来这个以 $i$ 结尾，总和为 $k$ 的目标串了。

3. 代码实现

▶

AcCode

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

const int maxn = 1e5 + 5;
const int maxs = 40 + 5;
const int inf = 0x3f3f3f3f;

int f[maxs][maxn];
int num[maxs][maxs];
// f[i][k] 表示 使用 S 的前 i 个字符，总和为 k 的最小操作次数
string s;
int n;

int calc( int l, int r )
{
    int res = 0;
    for( int i = l; i <= r; ++ i ) 
    {
        res = res * 10 + s[i] - '0';
        if( res > n ) return inf;
    }
    return res;
}

int main( )
{
    cin >> s >> n;

    int len = s.length( );
    s = ' ' + s;

    memset( f, 0x3f, sizeof( f ) );
    f[0][0] = 0;

    for( int i = 1; i <= len; ++ i )
    {
        for( int j = 0; j < i; ++ j )
        {
            int val = calc( j + 1, i );
            if( val > n ) continue;

            for( int k = val; k <= n; ++ k )
            {
                if( f[j][k - val] == inf ) continue;
                f[i][k] = min( f[i][k], f[j][k - val] + 1 );
            }
        }
    }

    int ans = f[len][n];
    if( ans > len ) cout << -1 << '\n';
    else cout << ans - 1 << '\n';

    return 0;
}

4. 复盘

• 复杂度分析：$O( |s| \cdot N )$。

• 碎碎念：子段划分型DP，本题注意剪枝即可。

• 关联笔记：线性DP