各位洛谷大佬们，能提供深搜思路，伪代码吗

学术版

Dream__Sky @ 2022-07-04 16:29:12

4.三角形(triangle)

题目描述

小魏有 3*n 根颜色两两不同的木棍，第i根的长度为a[i]。

小魏想把这3*n根木棍分成n组，每组三根，并且同一组的三根木棍可以组成一个三角形。

小魏想知道他有多少种不同的分组方案。认为两个分组方案是不同的,当且仅当两种方案组出来的三角形是不同的。

输入

第一行一个整数n。

第二行n个整数a[i]。

输出

一行一个整数，表示方案数。

样例输入输出

输入

2

3 4 5 10 11 12

输出

1

提示

对于20% 的数据，n=1；

对于50% 的数据，n≤3；

对于70% 的数据，n≤4；

另有10% 的数据，所有a[i] 全部相等；

对于所有数据，1≤n≤5, 1≤a[i] ≤100。

by thomaswmy @ 2022-08-16 14:10:58

@金宇昂 我做过这题

把我的代码放这吧

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int n,a[100];
int nxt[100],pre[100];
int head=1;
ll ans;
int an[100];

void dfs(int dep,int sum,int lst) {
    if(dep>n*3) {
        ans++;
        return ;
    }
    if(dep%3==0) {
        for(int i=lst;a[i]<sum && i<=n*3;i=nxt[i]) {
            nxt[pre[i]]=nxt[i];
            pre[nxt[i]]=pre[i];
            an[dep]=i;
            if(i==head) {
                head=nxt[i];
                dfs(dep+1,0,head);
                nxt[pre[i]]=i;
                pre[nxt[i]]=i;
                head=i;
            }
            else {
                dfs(dep+1,0,head);
                nxt[pre[i]]=i;
                pre[nxt[i]]=i;
            }
        }
    }
    else if(dep%3==2){
        for(int i=lst;i<=n*3;i=nxt[i]) {
            nxt[pre[i]]=nxt[i];
            pre[nxt[i]]=pre[i];
            an[dep]=i;
            if(i==head) {
                head=nxt[i];
                dfs(dep+1,sum+a[i],nxt[i]);
                nxt[pre[i]]=i;
                pre[nxt[i]]=i;
                head=i;
            }
            else {
                dfs(dep+1,sum+a[i],nxt[i]);
                nxt[pre[i]]=i;
                pre[nxt[i]]=i;
            }
        }
    }
    else {
        int i=head;
        nxt[pre[i]]=nxt[i];
        pre[nxt[i]]=pre[i];
        head=nxt[i];
        an[dep]=i;
        dfs(dep+1,sum+a[i],nxt[i]);
        nxt[pre[i]]=i;
        pre[nxt[i]]=i;
        head=i;
    }
}

int main() {
    scanf("%d",&n);
    for(int i=1;i<=n*3;i++) {
        scanf("%d",&a[i]);
        nxt[i]=i+1,pre[i]=i-1;
    }
    sort(a+1,a+1+n*3);
    dfs(1,0,1);
    printf("%lld",ans);
    return 0;
}

我加了一些优化，跑的很快

by thomaswmy @ 2022-08-16 14:13:58

优化是：

  1. 给木棍排序，这样搜第三根木棍时遇到第一个两边之和小于等于第三边就可退出

  2. 链表快速找下一个未放过的木棍

  3. 在搜第一根木棍时直接用最小的

by Dream__Sky @ 2022-08-16 14:15:16

@thomaswmy 感谢

|