USACO ORZ（DFS+set去重）
鏈接
2、題目描述

Like everyone, cows enjoy variety. Their current fancy is new shapes for pastures. The old rectangular shapes are out of favor; new geometries are the favorite.

I. M. Hei, the lead cow pasture architect, is in charge of creating a triangular pasture surrounded by nice white fence rails. She is supplied with N fence segments and must arrange them into a triangular pasture. Ms. Hei must use all the rails to create three sides of non-zero length. Calculating the number of different kinds of pastures, she can build that enclosed with all fence segments.

Two pastures look different if at least one side of both pastures has different lengths, and each pasture should not be degeneration.

輸入

The first line is an integer T(T<=15) indicating the number of test cases.

The first line of each test case contains an integer N. (1 <= N <= 15)

The next line contains N integers li indicating the length of each fence segment. (1 <= li <= 10000)

輸出

For each test case, output one integer indicating the number of different pastures.

樣例輸入

1

3

2 3 4

樣例輸出

1

題目大意
給定N個圍欄，形成多少個不同的三角形，要求是N個圍欄全部用上。這里不同的三角形指的是最少有一條邊不同。

題解
深度優先搜索DFS(int a,int b,int c, int step,int n,int nums[])
形參是三條邊a,b,c（要求a<=b<=c，方便處理）step是添加第step個圍欄，n是全部圍欄數量，nums是圍欄長度數組。

深搜的循環節如下,意思是深搜的下一次決策可能是下面的某一種。

//把第step個圍欄加到最短的邊上DFS(a+nums[step],b,c,step+1,n,nums);//把第step個圍欄加到次短的邊上DFS(a,b+nums[step],c,step+1,n,nums);//把第step個圍欄加到最長的邊上DFS(a,b,c+nums[step],step+1,n,nums);

那退出條件呢？
當然是step==n,所用圍欄數等于圍欄總數。滿足我們三角形的假設：三條邊a,b,c滿足兩邊之和大于第三邊a+b>c（要求a<=b<=c，方便處理）,此處采用小技巧，把a,b,c三個變量通過多項式乘法$(a{c}_0^2+b{c}_0+c)$ 轉換成為一個唯一變量,這樣用集合set統計個數即可。
注意這里c0不能亂取，太小的話容易造成重復，c0應該大一點，這里取數組中所有元素之和。
上代碼

if(step==n){//滿足三角形的基本條件if(a<=b&&b<=c&&a!=0&&b!=0&&c!=0&&a+b>c)//要保存到set中ans.insert(a*c0*c0+b*c0+c);return;//返回別忘記！}

深搜的調用DFS(0,0,0,0,N,a);意思是三條邊從0開始，a=0,b=0,c=0，step表示第0條圍欄，N表示圍欄總數目，a表示存放圍欄長度的數組。

全部代碼

#include<iostream> #include<set> #include<algorithm> using namespace std;int T,N,a[20]; //不能使用數組，這樣有邊重復 set<int> s; set<int> ans; int c0=0; void DFS(int a,int b,int c,int step,int n,int nums[]){if(step==n){if(a<=b&&b<=c&&a!=0&&b!=0&&c!=0&&a+b>c)ans.insert(a*c0*c0+b*c0+c);return;}DFS(a+nums[step],b,c,step+1,n,nums);DFS(a,b+nums[step],c,step+1,n,nums);DFS(a,b,c+nums[step],step+1,n,nums);}int main(){cin>>T;while(T--){ans.clear();cin>>N;for(int i=0;i<N;i++){cin>>a[i];c0+=a[i];//s.insert(a[i]);//放到集合中，沒有重復 }DFS(0,0,0,0,N,a);cout<<ans.size()<<endl;}}

當然上述代碼沒有記錄具體的解決方案，即每條邊的取值。

總結

以上是生活随笔為你收集整理的HDU-4277USACO ORZ深搜+set去重的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。