重庆师范大学第一届ACM选拔赛 B-有趣的求和

分析

这道题数据范围较小,看题目问题,可确定是一个dfs,每次要么走'-',要么走'+',时间复杂度
大概为O( ),可以小剪枝一下,如果当前加上所有的数如果都小于最后一个数,就不用搜了,
或者是减去后面所有数都大于最后的数,也不用再搜下去了

代码

//#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops")
//#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt")

/*
(写点什么吧...)
*/
#include<bits/stdc++.h>

#define R register
#define ll long long
#define inf INT_MAX

using namespace std;

const int N=22;
const ll mod=1e9+7;

int n,m,las,p;
int a[N],sum[N];
char ans[N];

vector<string>q;

inline void dfs(int now,int tot)
{
    //剪枝
    if(now==n)
    {
        if(tot==las)
        {
            p++;
            string s="";
            for (int i=2;i<=m;i++) s+=ans[i];
            q.push_back(s);
        }
        return ;
    }
    if(tot+sum[m]-sum[now-1]<las) return ;
    if(tot-(sum[m]-sum[now-1])>las) return ;

    ans[now]='-';
    dfs(now+1,tot-a[now]);
    ans[now]='+';
    dfs(now+1,tot+a[now]);
}

int main()
{
    scanf("%d",&n);m=n-1;
    for (int i=1;i<n;i++) scanf("%d",&a[i]);
    scanf("%d",&las);
    for (int i=1;i<=m;i++) sum[i]=sum[i-1]+a[i];

    dfs(2,a[1]);

    printf("%d\n",p);
    for (int i=0;i<p;i++)
        cout<<q[i]<<"\n";

    return 0;
}