P1874 快速求和题解

KidA · 2023-10-12 20:57:08 · 题解

upd on 2023/12/22：修改了代码，现已通过所有 hack 数据。

首先定义状态：

令 dp_{i,j} 表示前 i 个数字要变成 j 所需要的最少加号个数。
同时，我们还需要一个辅助数组：令 num_{i,j} 表示 i \sim j 的数字组成的数（不添加加号）。

然后进行转移。

显然可以枚举每个添加加号的位置 i，再枚举当前位置与上一个添加加号的位置的距离 k，然后枚举前 i 个数要变成的数 j，于是易得转移方程：

dp_{i,j}=\min(dp_{i,j},dp_{i-k,j-num_{i-k+1,i}}+1)

朴素转移即可。

注意特判 dp_{len,n}>len（len 表示字符串 s 的长度）的情况。

时间复杂度 O(n \times len)。

需要注意字符串中的 0 需要剔除，在全 0 的情形下会影响答案。

代码：

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;

string str;
int s,n,tot;
int a[100031];
int num[55][55];
int dp[55][100031];
bool z;

signed main(){
    srand(time(0));
    cin>>str>>s;
    n=str.size();
    for(int i=0;str[i];i++){
        if(str[i]!='0') z=1;
        if(z) a[++tot]=str[i]-'0';
    }
    for(int i=1;i<=tot;i++){
        num[i][i]=a[i];
        for(int j=i;j-i<=11&&j<=tot;j++)
            num[i][j]=num[i][j-1]*10+a[j];
    }
    for(int i=0;i<=tot+1;i++)
        for(int j=0;j<=s+1;j++)
            dp[i][j]=0x7fffffff;
    dp[0][0]=0;
    for(int i=1;i<=tot;i++)
        for(int k=1;k<=11;k++)
            if(i>=k)
                for(int j=num[i-k+1][i];j<=s;j++)
                    dp[i][j]=min(dp[i][j],dp[i-k][j-num[i-k+1][i]]+1);
    if(dp[tot][s]>tot) cout<<-1;
    else cout<<dp[tot][s]-1;
    return 0;
}

P1874 快速求和 题解

P1874 快速求和题解