Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

求助高手帮忙看一下 论坛上的测试数据都过了 实在没办法了

Posted by 2016213435 at 2019-04-14 11:40:25 on Problem 2362
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int sticks[22];
bool mark[22];
int length;
int num;
int flag;
int cmp(int a, int b){
    return a > b;
}
void dfs(int begin, int sum, int step){
    if(step == 3) {
        flag = 1;
        return;
    }
    if(flag == 1){
        return;
    }
    int nsum;
    for (int i = begin; i <= num; ++i) {
        if(mark[i] == true) continue;
        nsum = sum + sticks[i];
        if(nsum > length) continue;
        if(nsum == length){
            mark[i] = true;
            dfs(1, 0, step + 1);
            mark[i] = false;
            if(flag == 1){
                return;
            }
        }

        if(nsum < length){
            mark[i] = true;
            dfs(i + 1, nsum, step);
            mark[i] = false;
            if(flag == 1){
                return;
            }

        }
    }
}
int main(){
    int n;
    scanf("%d", &n);
    while (n --){
        memset(sticks, 0, sizeof(sticks));
        memset(mark, false, sizeof(mark));
        int sum = 0;
        flag = 0;
        scanf("%d", &num);
        for (int i = 1; i <= num; ++i) {
            scanf("%d", &sticks[i]);
            sum += sticks[i];
        }
        sort(sticks + 1, sticks + num + 1, cmp);
        length = sum / 4;
        if( num < 4 ){
            printf("no\n");
            continue;
        }
        dfs(1, 0, 0);
        if(flag == 1){
            printf("yes\n");
        } else{
            printf("no\n");
        }
    }
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator