dfs样例过但是全WA,真是一场灾难
查看原帖
dfs样例过但是全WA,真是一场灾难
1217330
xdedb楼主2024/1/4 19:57

题目中的样例本地可以过,然后讨论区我看到的

6 6 6 6
1 1 4 4 2 2
1 1 4 4 2 2
1 1 4 4 2 2
1 1 4 4 2 2

这个也可以过 实在看不出自己的问题了,感觉自己搜索学的笨笨的,求大佬们指教。

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

double des;
double the;

void dfs(int last,int num,int to,int * arr);

int main(){
    int s[4];
    int ans=0;
    for(int i=0;i<4;i++){
        cin>>s[i];
    }
    for(int i=0;i<4;i++){
        the=60;
        int tn,tol=0;
        tn=s[i];
        int time[tn];
        for(int t=0;t<tn;t++){
            cin>>time[t];
            tol+=time[t];
        }
        sort(time,time+tn);
        des=(double)tol/2;
        dfs(0,-1,tn,time);
        ans+=the;
    }
    cout<<ans;
}

void dfs(int last,int num,int to,int * arr){
    int la=last;
    for(int i=num+1;i<to;i++){
        la=last+arr[i];
        if(la<des){
            dfs(la,i,to,arr);
        }else{
            if(la<the){
                the=la;
            }
            return;
        }
    }
}
2024/1/4 19:57
加载中...