题解 P1874 【快速求和】

· · 题解

本题思路非常明确：在所有能插入加号的位置枚举加号是否存在，对于每一种情况，若求得和为n则更新答案。

但是看看数据规模。。。长度<=40，也就是说枚举的时间最多可达2^39，显然会T，所以需要剪枝。

剪枝1：若整串拆分为单个数字后求和，所得结果>n，则一定无解。

原因：显然在一次拆分后，新生成的数字的和不会比未拆分之前的大（不要问我为什么，这是直觉）。

那么对于某个串，它对应的和最小的拆分方案即为：将其拆分为单个数字。

于是乎，整串对应的最小的和都>n，那么就不可能有可行解了。

剪枝2：若将未处理部分作为一个数字与已处理部分相加，所得的和<n，则在此递归子树中一定无解。

原因：类比一下剪枝1，可得：对于某个串，它对应的和最大的拆分方案为：直接将其转化为数字，即不拆分（不要问我为什么，这也是直觉）。

那么，将未处理部分作为一个数字与已处理部分相加，就是此递归子树中对应和最大的方案。

如果最大的和都<n，那么就不可能有可行解了。

剪枝3：若当前加号数量>=ans，则此递归子树中无更优解。这一点十分显然。

剪枝4：若将未处理部分拆分为单个数字后与已处理部分求和，所得的和>n，则在此递归子树中一定无解。

原因：同剪枝1。

剪枝5：若找到一个可行解，则此递归子树中无更优解。再搜下去，加号会增多，一定得不到比此可行解更优的解。

实现细节及剪枝位置详见代码及注释。

#include<cstdio>
#include<cstring>

using namespace std;

void dfs(int,int,int);
inline int val(int,int);  //将某子串转化为数字 
inline int min(int,int);
inline int qh(int,int);  //将某子串拆分为单个数字后求和 

char s[50];
int a[50],l,ans=2147483647,sum=0,n;

int main(){
    scanf("%s",s+1);
    scanf("%d",&n);
    l=strlen(s+1);
    for(int i=1;i<=l;i++){
        a[i]=s[i]-'0';
        sum+=a[i];
    }
    if(sum>n){
        printf("-1\n");  //剪枝1 
        return 0;
    }
    else{
        dfs(0,0,0);
        if(ans==2147483647)printf("-1\n");
        else printf("%d\n",ans);
    }

    return 0;
}

void dfs(int res,int p,int dep){  //res：已处理部分的和 p：标记已经处理到何处 dep：加号数量 
    int temp=res+val(p+1,l);  //将未处理部分作为一个数字与已处理部分相加
    if(temp<n)return;  //剪枝2 
    if(dep>=ans)return;  //剪枝3 
    if(res+qh(p+1,l)>n)return;  //剪枝4 
    if(temp==n){  //找到可行解 
        ans=min(ans,dep);  //更新答案 
        return;  //剪枝5 
    }
    for(int i=p+1;i<l;i++){
        temp=res+val(p+1,i);
        dfs(temp,i,dep+1);
    }
}

inline int val(int l,int r){
    int ans=0;
    for(int i=l;i<=r;i++)ans=(ans<<3)+(ans<<1)+a[i];
    return ans;
}

inline int min(int x,int y){
    if(x<y)return x;else return y;
}

inline int qh(int l,int r){
    int ans=0;
    for(int i=l;i<=r;i++)ans+=a[i];
    return ans;
}