求助!深搜除了2和7过了其他全部tle
查看原帖
求助!深搜除了2和7过了其他全部tle
823227
lightmon楼主2022/12/30 19:54
#include <iostream>
#include <algorithm>
#include <numeric>
#include <cstring>

using namespace std;

const int N = 25;
int st[N];
int res = 0x3f3f3f3f, ans;
int arr[N];
int num[5];

void dfs(int n, int s, int ss){
    if(s <= 0){
        res = min(res, ss - s);
        return;
    }
    for(int i = 0; i < n; i ++){
        if(!st[i]){
            st[i] = 1;
            s -= arr[i];
            dfs(n, s, ss);
            st[i] = 0;
            s += arr[i];
        }
    }
}

int main(){
    for(int i = 1; i <= 4; i++) cin >> num[i];
    for(int i = 1; i <= 4; i++) {
        for (int j = 0; j < num[i]; j++) {
            cin >> arr[j];
        }
        memset(st, 0, sizeof st);
        res = 0x3f3f3f3f;
        int s;
        if(accumulate(arr, arr + num[i], 0) % 2 == 0)
            s = accumulate(arr, arr + num[i], 0) / 2;
        else s = accumulate(arr, arr + num[i], 0) / 2 + 1;
        dfs(num[i], s, s);
        ans += res;
    }
    cout << ans;
    return 0;
}
2022/12/30 19:54
加载中...