本文主要是介绍[DP]三角形牧场，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
三角形牧场
时间限制: 1 Sec 内存限制: 128 MB
题目描述
和所有人一样，奶牛喜欢变化。它们正在设想新造型的牧场。奶牛建筑师Hei想建造围有漂亮白色栅栏的三角形牧场。她拥有N(3≤N≤40)块木板，每块的长度Li(1≤Li≤40)都是整数，她想用所有的木板围成一个三角形使得牧场面积最大。
请帮助Hei小姐构造这样的牧场，并计算出这个最大牧场的面积。
输入
第1行：一个整数N
第2..N+1行：每行包含一个整数，即是木板长度。
输出
仅一个整数：最大牧场面积乘以100然后舍尾的结果。如果无法构建，输出-1。
样例输入
5
1
1
3
3
4
样例输出
692
样例解释
692=舍尾后的(100×三角形面积)，此三角形为等边三角形，边长为4。
题解
- 从n个里分成三组
- 但贪心不能最优
- 所以，选出所有成立的边长，找最大面积
- dp[i,j,k]:前i个里面，分出一组总长j和一组总长k的（剩下一组长度就能知道了）是否是可行的（可行即为1，反之则为0）
- dp[i,j,k]是由三种决策达到的，即x[i]放在j组/k组/sum-j-k组
- 注意初始化，以及递推式的数组下标不越界
vardp:array[0..100,0..800,0..800]of integer;x:array[0..100]of longint;s,p:real;i,j,k:longint;n,sum,t,l:longint;m:string;
beginreadln(n);for i:=1 to n dobeginreadln(x[i]);inc(sum,x[i]);end;for i:=0 to n dodp[i,0,0]:=1;for i:=1 to n dobeginfor j:=x[i] to sum div 2 dofor k:=0 to sum div 2 doif (dp[i-1,j-x[i],k]=1)then dp[i,j,k]:=1;for j:=0 to sum div 2 dofor k:=x[i] to sum div 2 doif (dp[i-1,j,k-x[i]]=1)then dp[i,j,k]:=1;for j:=1 to sum div 2 dofor k:=1 to sum div 2 doif dp[i-1,j,k]=1then dp[i,j,k]:=1;end;p:=sum/2;s:=-1;for j:=1 to (sum div 2) dofor k:=1 to (sum div 2) doif (dp[n,j,k]=1)and(j+k>sum-j-k)and(sum-k>k)and(sum-j>j)then s:=max(s,sqrt(p*(p-j)*(p-k)*(p-sum+j+k)));if s<0then writeln(-1)elsebeginstr(s*100:0:2,m);m:=copy(m,1,length(m)-3);writeln(m);end;
end.这篇关于[DP]三角形牧场的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
