题解 P1874 【快速求和】

只用函数 · 2018-10-20 00:23:56 · 题解

暴力深搜

关键是此题数据不用剪枝......

咳咳咳，这道题我采用的是回溯，回溯的内容是1~K个加号的组合。

一旦有情况的值==n，即可输出i。

重要内容请看代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>
using namespace std;
string st;
long long n,i;
long long book[55];
bool f;
void dfs(long long k)//明明是组合，却被我写成了排列
{
    if(k==i)
    {//重点啊重点啊（敲黑板）
        long long ans=0,sum=st[0]-'0';//sum开始不为0，就使得一开始就有+号的情况能正好避免。
        for(int j=1;j<st.size();j++)
        {
            if(book[j]==0)sum=sum*10+st[j]-'0';//进位就不用我讲了吧
            else ans+=sum,sum=st[j]-'0';//ans累计这一段的和，而这时正好所对应的那个数字，sum就不用清零，直接等于那个数字。
        }
        ans+=sum;//最后没有加号，就要把最后一个加数加上。
        if(ans==n)f=true;
        return ;
    }
    for(int j=1;j<st.size();j++)
    {
        if(book[j]==0)
        {
            book[j]=1;
            dfs(k+1);
            book[j]=0;
        }
    }
}
int main()
{
    cin>>st>>n;
    for(i=0;i<st.size();i++)//要从0开始，可能正好这个字符串就是那个数字本身呢？（这里有10分）
    {
        memset(book,0,sizeof(book));
        f=false;
        dfs(0);//从0开始，就可满足字符串就是数字本身的情况。
        if(f==true)
        {
            cout<<i<<endl;//题目要求最少加号，所以一旦找到一个能使字符串变成n的，就可以输出了。
            return 0;
        }
    }
    cout<<-1<<endl;//别忘了输出-1（这里又有10分）
    return 0;
}

嗯，可能是应为本蒟蒻的语言组织能力不好，怕在座的各位同学听不懂，于是就有了下面的配图： 希望能对同学们理解本蒟蒻的程序有所帮助！