poj 1948 Triangular Pastures (dp二維背包)

題目大意：

給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+

代碼：

[cpp]
#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; 
} 

#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;
}