[数据结构与算法]拼三角（暴力dfs跑组合）

拼三角

• ?比赛主页
• ?我的提交

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述?

给出6根棍子，能否在选出3根拼成一个三角形的同时剩下的3根也能组成一个三角形？

输入描述:

首先在一行中给出一个 t,1≤t≤103t,1≤t≤103，代表测试数据的组数

接下来t行，每行给出6个数字代表棍子长度，棍子长度为正且小于109109

输出描述:

在一行中输出 “Yes” or “No”

示例1

输入

复制

2
1 1 1 1 1 1
1 2 3 4 5 6

输出

复制

Yes
No

int dp[2];
int a[6];
int b[3];
int c[3];
int vis[6];
int flag;
int check(int arr[]){
    int a=arr[0];
    int b=arr[1];
    int c=arr[2];
    if(a+b>c&&a+c>b&&b+c>a){
        return 1;
    }
    return 0;
}
void dfs(int now,int num){
    if(flag) return;
    if(num==3){
        if(check(b)){
            int cnt=0;
            for(int i=0;i<6;i++){
                if(!vis[i]){
                    c[cnt++]=a[i];
                }
            }
            if(check(c)){
                flag=1;
            }
        }
        return;
    }
    vis[now]=1;
    for(int i=now+1;i<6;i++){
        if(!vis[i]){
            vis[i]=1;
            b[num]=a[i];
            dfs(i,num+1);
            vis[i]=0;
        }
        else dfs(now+1,num);
    }
}
int main(){
    int t;
    cin>>t;
    while (t--) {
        flag=0;
        for(int i=0;i<6;i++){
            cin>>a[i];
        }
        dfs(-1,0);
        if(flag) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
}