题解 P1874 【快速求和】

孙某人 · 2018-05-12 12:23:18 · 题解

蒟蒻孙某人的第一篇题解，望管理员通过！######

本人的想法很简单：暴力深搜

好像也可以枚举，更加暴力

话不多说，代码分析

#include<bits/stdc++.h>//万能头文件，请先从int main下面看起 
using namespace std;
int a[50],shu,biao,sum,minn=10000000,len=1;
bool pd,plus_[50];
string ss;
int cr(int left,int right)//炒鸡有用，输入头尾，求中间这一段数的值 
{
    int yin=1,num=0;//yin是每位数的基数，num是总和 
    for(int i=right;i>=left;i--)
    {
        num+=a[i]*yin;
        yin*=10;
    }
    return num;
}
void dfs(int step,int sum)//step是当前数值的和，sum是加号数量 
{
    if(sum==minn)return;//如果sum已经等于加号最小值了，就返回，没必要再做，省时间 
    if(step==biao)//数值等于目标 
    {
        if(sum<minn)
        {
            minn=sum;
            pd=true;//pd表示的是最后是否能达到目标，决定输出-1还是minn 
        }
        return;
    }
    for(int i=1;i<len;i++)//表示在a[i]这个数字后，a[i+1]数字前加加号
    {
        if(plus_[i])continue;//plus数组表示此位置加号是否放置，未放置为false，已放置为true 
        plus_[i]=true;
        int f=0,start=1;
        for(int j=1;j<len;j++)//搜索加号，将几个部分加起来 
        if(plus_[j])
        {
            f+=cr(start,j);
            start=j+1;
        }
        f+=cr(start,len);//加上最后的部分 
        dfs(f,sum+1);//f为当前的值 
        plus_[i]=false;//回溯一步 
    }
}
int main()
{
    cin>>ss;//先用字符串读入。因为原数用数组保存方便很多！如用while（cin）会将目标数字也读入数组！    
    len=ss.size();
    for(int i=0;i<len;i++)a[i+1]=ss[i]-'0';//字符转整数  
    cin>>biao;//目标数 
    dfs(cr(1,len)/*求和函数，请看上面*/,0);//暴力深搜开始，请看上面 
    if(!pd)cout<<-1; 
    else cout<<minn;
    return 0;
}