poj1948（经典问题-二维背包求面积最大三角形）

题意：给n(n<=40)个木板，每个长度不超过40.问40条木板能够组成的最大三角形面积是多少。

解法：dp[i][j][k]表示前k个木板是否能够组成两个长度为i,j的组合，当然ij是相互没有重叠部分的。根据三角形的性质知道，i，j都不会大于等于周长的一半，所有取最大800就够了。滚动使用dp[i][j]可以将空间降到二维，为了避免i,j有重复使用同一个木板，从大向小反向dp。

代码：

/****************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              #include 
             
               using namespace std; #define eps 1e-8 typedef long long LL; int n; int num[110]; bool dp[810][810]; double getarea(double a,double b,double c) { double p=(a+b+c)/2.0; return sqrt(p*(p-a)*(p-b)*(p-c)); } bool OK(int a,int b,int c) { if(a+b<=c) return false; if(a+c<=b) return false; if(b+c<=a) return false; return true; } int main() { scanf("%d",&n); int sum=0; for(int i=0;i
              
               =0;k--) { for(int j=k;j>=0;j--) { if(k-num[i]>=0&&dp[k-num[i]][j]) dp[k][j]=1; if(j-num[i]>=0&&dp[k][j-num[i]]) dp[k][j]=1; } } } double ans=0; for(int i=0;i<=800;i++) for(int j=0;j<=i;j++) { if(dp[i][j]&&OK(i,j,sum-i-j)) ans=max(ans,getarea(i,j,sum-i-j)); } if(ans==0) cout<<"-1\n"; else cout<<(int)(ans*1000)/10<

poj1948（经典问题-二维背包 求面积最大三角形）