Cons. Marx
2022-03-27 14:51
采纳率: 94%
浏览 15

请问一下这应该怎么优化?我写的只能通过一半的数据

img

用了一定的剪枝,但是还是不能解决超时的问题,代码已附注释


#include<iostream>
#include<algorithm>
using namespace std;
int n,x;
int cnt=0;

void dfs(int start,int a[],int end,int cur,int sum)
//下面对dfs中的部分参数进行说明:
//start:代表每层循环中加数的开始位置,每一层循环的加数开始位置都应该是上一层循环的下一位(因为不能取同一个数,这类似于握手问题)
//end:最多有几个数相加,取决于主函数中for循环的i
//cur:当前这层递归处于那一层也就是说这是第几个数,如果不到end,那么就继续相加
//sum:记录当前的所加和,sum必须到最后一层递归时,才能去比较大小
{
    if(sum==x && cur==end){//如果递归到了最后一层,并且sum等于x,那么就让方案数加一
        cnt++;
        return;
    }
    else if(cur>end || sum>x) return;
    for(int i=start;i<n;i++) dfs(i+1,a,end,cur+1,sum+a[i]);
}

int main(){
    cin>>n>>x;
    int* b = new int[n];
    int ign = n;
    for(int i=0;i<n;i++){
        int t;
        cin>>t;
        if(t>x) continue;
        else if(t==x) {
            cnt++;
            continue;
        }
        else {
            b[i] = t;
            ign--;
        }
    }
    int* a = new int[n-ign];
    n-=ign;
    for(int i=0;i<n;i++) a[i] = b[i];
    sort(a,a+n,greater<int>());
    for(int i=1;i<=n;i++) dfs(0,a,i,1,0);//i代表有几个加数,如i=1就是只有一个数
    if(!cnt) cout<<"-1";
    else cout<<cnt;
}

1条回答 默认 最新

相关推荐 更多相似问题