题目链接https://www.luogu.com.cn/problem/P1284题目分析观察数据范围发现对于 100% 的数据保证。不难想到可以使用暴力 DFS。三角形判定三条边能组成三角形的充要条件是任意两边之和大于第三边。表示为且且。面积计算计算面积可以用 海伦公式暴力dfs设计 dfs参数为 层数 和 三边边长。暴力代码#includebits/stdc.h using namespace std; int n,q[45]; double ans; double S(int a,int b,int c){//海伦公式计算面积 double p (abc)*1.0/2; return sqrt(p*(p-a)*(p-b)*(p-c)); } void dfs(int s ,int a ,int b ,int c){ if(sn){ if(abcbcaacb) ans max(100.0*S(a,b,c),ans); return; } dfs(s1,aq[s],b,c); dfs(s1,a,bq[s],c); dfs(s1,a,b,cq[s]); } int main(){ cinn; for(int i 1;in;i) cinq[i]; dfs(1,0,0,0); printf(%d,(int)(ans0?-1:ans)); return 0; }当然纯暴力 dfs 必定会 TLE 36pts。剪枝注意到对于三角形的三条边不管三边的排列如何只会有一个解面积同时由此三条边所推出的解**不因**三条边的排列顺序而改变。发现可以剪枝对于三条边**去重**。又发现在同一层时一定满足**任意两边一定另一条边长度唯一**。唯一性证明当层数为第层时定义。在同一层 $s$ 下为常数故给定 $mx$ 和 $mn$ 后中间边也被唯一确定。考虑维护一个数组 $vis$对于唯一确定。由于木板长度 $l$ 和 数量 $n$ 较小可直接开数组。即。维护标记数组进行剪枝即可。时间复杂度令总周长记忆化剪枝保证每种状态值被访问了一次所以时间复杂度因为在实际情况中访问次数实际是远小于的因此是可行的。代码#includebits/stdc.h using namespace std; int n,q[45]; bool vis[42][1602][1602]; double ans; double S(int a,int b,int c){//海伦公式求面积 double p (abc)*1.0/2; return sqrt(p*(p-a)*(p-b)*(p-c)); } //mx最大值、mn最小值 void dfs(int s,int a,int b,int c){ if(vis[s][max({a,b,c})][min({a,b,c})]) return; vis[s][max({a,b,c})][min({a,b,c})] 1; if(sn){ if(abcbcaacb){ ans max(100.0*S(a,b,c),ans); } return; } //枚举每种方式 dfs(s1,aq[s],b,c); dfs(s1,a,bq[s],c); dfs(s1,a,b,cq[s]); } int main(){ scanf(%d,n); for(int i 1;in;i) scanf(%d,q[i]); dfs(1,0,0,0); printf(%d,(int)(ans0?-1:ans)); return 0; }