算法：poj 1948 Triangular Pastures (dp 二维01背包)

题目大意：

给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_pair
const 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\n", (int)(100*ans));  

    return 0;
}

查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索1602
， int
， 优化
， include
， 三角形面积计算
， double
， 三角形
二维
二维dp、pastures、greener pastures、triangular arbitrage、triangular，以便于您获取更多的相关知识。