题解 P1874 【快速求和】

Dog_Two · 2018-10-15 22:16:50 · 题解

考虑迭代加深的搜索方式。

我们从0开始枚举可能的答案，然后进行搜索。

有三个显然的剪枝，运用之后可以提升程序的效率(仍然很慢)，但编码（和思维）难度并没有提升。

• 当尝试的cnt>ans时，剪枝；
• 当把后面的所有数字都拆成一位数字相加（可以证明，这样处理后，字符串的和最小）仍然大于n时，剪枝；
• 当把后面的数字去掉前导0后，视作一整个数字相加（可以证明，这样处理后，字符串的和最大）仍然不足n时，剪枝；

对于剪枝2，我们维护一个后缀和数组sum；

对于剪枝3，我们实现一个（套）函数：它支持在一个数字字符串里找到一个子段并将其转换成数字。

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

char line[41];
int sum[42];
int n,l;

inline int num(const int &l,const int &r){
    int res=0;
    for(int i=l+1;i<=r;++i) res=res*10+line[i]-'0';
    return res;
}

inline bool enough(const int &last,const int &val){
    int i;
    for(i=last+1;line[i]-'0'==0;++i);
    if(l-i+1>=9) return true;
    return num(i-1,l)>=n-val;
}

int ans;

bool dfs(int last,int cnt,int val){
    if(cnt>ans) return false;//1
    if(last==l) return val==n; 
    if(val+sum[last+1]>n) return false;//2
    if(!enough(last,val)) return false;//3
    for(int now=last+1;val+num(last,now)<=n;++now)
        if(dfs(now,cnt+(now!=l),val+num(last,now))) return true;
    return false;
}

void read(){
    scanf("%s %d",line+1,&n);
    l=strlen(line+1);
    for(int i=l;i;--i) sum[i]=sum[i+1]+line[i]-'0';
}

void solve(){
    for(ans=0;!dfs(0,0,0) and ans<l;++ans);
    cout<<(ans==l?-1:ans);
}

int main(){
    read();
    solve();
    return 0;
}