题解 P1284 【三角形牧场】

Jacob233 · 2017-09-19 20:34:17 · 题解

DP，只需开二维数组存此三角形的两条边，就可以表示出第三条边，再判断能否加上这根木棒

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=40+5;
int a[maxn];
bool f[888][888];//吉利数字保AC（其实是可以从数据看出最大周长为1600，每条边长度显然不能超过800）
int n;
double maxx=-1;
bool Tri(int i,int j,int k){
    if(i+j>k&&i+k>j&&k+j>i)return true;
    else return false;

}//判断是否可以构成三角形

double Helen(double i,double j,double k){
    double p;
    p=(i+j+k)/2;
    return sqrt(p*(p-i)*(p-j)*(p-k));

}//海伦公式算面积

int main(){
    while((scanf("%d",&n))!=EOF){
        memset(a,0,sizeof(a));
        memset(f,false,sizeof(f));
        int tot=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            tot+=a[i];//处理出周长
        }
        int half=tot/2;//从周长一半开始循环，很显然三角形的每一条边不可以超过周长的一半
        f[0][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=half;j>=0;j--){
                for(int k=j;k>=0;k--){
                    if(j>=a[i]&&f[j-a[i]][k] || k>=a[i]&&f[j][k-a[i]])f[j][k]=1;//若是能够加上这根小木棒则赋值为1，f[j][k]表示能否组成边长为j,k的边，也要注意判断它加过来之前的那个f是否存在
                }
            }
        }
        for(int i=half;i>=1;i--){
            for(int j=i;j>=1;j--){
                if(f[i][j]){
                    int k=tot-i-j;
                    if(Tri(i,j,k)){
                        double val=Helen(i,j,k);
                        if(val>maxx)maxx=val;
                    }
                }
            }
        }
        if(maxx==-1)cout<<-1<<endl;//无法组成的情况
        else cout<<(int)(maxx*100)<<endl;//记得最后结果是整数并且要 *100
    }
    return 0;
}