poj1948专题

POJ1948 Triangular Pastures(01背包)

题意: 输入一些栏杆,可以相互拼接,要求拼成一个面积最大的三角形 要点: 已知三角形三边可以用海伦公式计算三角形面积:S=√[p(p-a)(p-b)(p-c)],p=(a+b+c)/2。因为总长确定,所以确定两条边就可以知道第三条边,用背包的思路,dp[i][j]为1,表示从这些线段中可以组成一个边长为i,另一边为j的三角形;为0则表示不能。这里的二维相当于三维降一维以节约内存空间。