随笔-141  评论-9  文章-3  trackbacks-0
pku 1948 Triangular Pastures (01背包)

1. 在三角形的周长l一定时，最长边c的取值范围是l/3≤c＜l/2

2. 用01背包枚举两条边.

#include <iostream>
#include <cmath>

using namespace std;

bool f[1000][1000];
int len[50];
int N;

double area(int a, int b, int c){
    double p = (a+b+c)/2.0;
    return sqrt(p*(p-a)*(p-b)*(p-c));    
}

int main(){
    int i,j,k,sum=0;
    double ans = 0.0 ;//,tmp=0.0;
    cin>>N;

    for(i=1; i<=N; ++i){
        cin>>len[i];
        sum+=len[i];
    }

    int max = sum/2;

    f[0][0]=true;

    for(i=1; i<=N; ++i)
        for(j=max; j>=0; j--)
            for(k=max; k>=0; k--)
                f[j][k] = f[j][k] | (j>=len[i]&&f[j-len[i]][k]) |(k>=len[i]&&f[j][k-len[i]]);

    for(i=1; i<=max; ++i)
        for(j=1; j<=max; ++j)
            if(f[i][j]){
                k = sum-i-j;
                if( (i+j>k) && (i+k>j) && (k+j>i) ){
                    double tmp = area(i,j,k);
                    if(tmp>ans)
                        ans = tmp;
                }

            }

    if(ans == 0.0)
        cout<<-1<<endl;
    else
        cout<<(int)(ans*100)<<endl;

    //system("pause");
    return 0;

}
posted on 2010-12-09 11:07 小阮 阅读(336) 评论(1)  编辑 收藏 引用 所属分类: POJ

评论:
# re: pku 1948 Triangular Pastures (01背包) 2011-05-18 23:31 | 陨儿52000
能不能告诉我样例输入和输出是咋回事，咋就得到那么大的面积，谢谢了  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 小阮