算法：poj 1948 Triangular Pastures （dp 二维01背包）

算法：poj 1948 Triangular Pastures （dp 二维01背包）2014-01-10 csdn shuangde800题目大意：

给N条边，把这些边组成一个三角形，问面积最大是多少？必须把所有边都用上。

思路：

对于已知周长的三角形，我们只要知道两条边的长度变可推出第三条边，所以可以得到状态方程：

f[i][j][k] 表示用前i条边，能否组成长度为j和k的两条边

初始化f[0][0][0] = true；

f[i][j][k] = f[i-1][j-len[i]][k] || f[i-1][j][k-len[i]];

如果f[i][j][k]=true ，那么就计算以j,k,sum-j-k为三条边能否组成三角形，如果可以就用海伦公式计算面积。

由于如果要开三维数组的话，要开f[40][1600][1600],明显是要MLE的，所以要降成二维的，

而时间复杂度40*1600*1600,如果没有优化直接上，是要TLE的。

所以要优化，根据优化的程度，运行时间可以再100MS~1000MS之间：

1. f[i][j] 和 f[j][i]是相同的两个三角形，所以递推时可以让 j>=i

2. 对于每条边，一定是小于周长的一半

3. 枚举到第i条边时，前i条边不可能组成大于等于sum[i] （sum[i]=len[1]+...+len[i]）的长度

优化了一下时间到了100MS+

代码：

#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<cstring>#include<vector>#define SQ（x） （（x）*（x））#define MP make_pairconst int INF = 0x3f3f3f3f;const double PI = acos（-1.0）;typedef long long int64;using namespace std;const int MAXN = 42;int n, m;int len[MAXN], sum[MAXN];bool f[1602][1602];inline bool isTriangle（double e[3]）{if（e[2] < e[1]）{swap（e[2], e[1]）;if（e[1] < e[0]） swap（e[0], e[1]）;}return e[0]+e[1] > e[2];}inline double getArea（double e[3]）{if（！isTriangle（e）） return -1;double p = sum[n]/2.0;return sqrt（p*（p-e[0]）*（p-e[1]）*（p-e[2]））;}int main（）{scanf（"%d", &n）;for（int i=1; i<=n; ++i）{scanf（"%d", &len[i]）;sum[i] = sum[i-1]+len[i];}memset（f, 0, sizeof（f））;f[0][0] = true;double ans = -1;double e[3];for（int i=1; i<=n; ++i）{for（int v1=min（sum[i],sum[n]>>1）; v1>=0; --v1）{for（int v2=min（sum[i]-v1,sum[n]>>1）; v2>=v1; --v2）if（v1+v2<sum[n]）{e[0] = v1; e[1] =v2; e[2] = sum[n]-v1-v2; if（v1-len[i]>= 0 && f[v1-len[i]][v2]）{f[v1][v2] = true;}if（！f[v1][v2] && v2-len[i]>=0 && f[v1][v2-len[i]]）{f[v1][v2] = true;}if（f[v1][v2]）{ans = max（ans, getArea（e））; }} }}if（ans < 0） puts（"-1"）;else printf（"%d
", （int）（100*ans））;return 0;}