POJ 1948 Triangular Pastures[二维01背包]
给最多40根木棍,每根长度不超过40, 要用完所有的木棍构成面积最大的三角形, 求出最大的面积。
算法核心
二维01背包
使用到海伦公式:
已知三角形的三边长度a,b,c,求面积 S=√[p(p-a)(p-b)(p-c)] 而公式里的p为半周长: p=(a+b+c)/2
分析:
用dp[i][j][k]表示到第i根木棒能否摆出边长分别为j,k的三角形 易得
dp[i][j][k] = dp[i-1][j-x[i]][k]|dp[i-1][j][k-x[i]]|dp[i-1][j][k];
简单的 空间压缩,化为二维dp,注意:这里每根木棒只能使用一次, 是01背包,要倒着扫(刚开始错在这里了。。。)
Read full article from POJ 1948 Triangular Pastures[二维01背包]
No comments:
Post a Comment