VOJ 等边三角形 题解 DFS

等边三角形

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, flag = 0, sum = 0, tag;
int length[20];     // 木棍长度
int group[3] = {0}; // 三条边的当前边长
void dfs(int i, int index)
{
    group[index] += length[i];
    if (group[1] > tag || group[0] > tag || group[2] > tag) // 剪枝：一旦有一条边长度大于预期边长tag，该方案不满足
    {
        group[index] -= length[i]; // 回溯
        return;
    }
    if (group[0] == tag && group[1] == tag) // 一旦有两条边可以达到预期边长tag，则可以构成等边三角形
    {
        flag = 1;
        return;
    }
    if (i + 1 < n) // 判断：如果没有遍历完所有木棍，则继续递归，否则终止递归
    {
        // 递归下一根木棍放到三条边中的三种情况
        if (!flag)
            dfs(i + 1, 0);
        if (!flag)
            dfs(i + 1, 1);
        if (!flag)
            dfs(i + 1, 2);
    }
    group[index] -= length[i]; // 回溯
    return;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n; // 木棍数量
    for (int i = 0; i < n; i++)
    {
        cin >> length[i];
        sum += length[i]; // 统计总长度
    }
    tag = sum / 3;    // 等边三角形边长
    if (sum % 3 == 0) // 总长度能被3整除是能构成等边三角形的前提
        dfs(0, 0);
    if (flag)
        cout << "yes";
    else
        cout << "no";
    return 0;
}