[POJ] 1948 Triangular Pastures (DP)

题目地址：http://poj.org/problem?id=1948

题目大意：

给N条边，把这些边组成一个三角形，问面积最大是多少？必须把所有边都用上。

解题思路：

根据题意周长c已知，求组合三边长使得三角形面积最大。如果直接DFS的话，每次考虑每根木棍放在哪一条边上，爆搜，可以加上每条边不会大于周长的一半的剪枝。根据数据规模，仍会超时，所以可以考虑采用动态规划。因为周长c已知，所以只需考虑其中两条边即可。类似二维0-1背包的做法，开一个二维判定数组f[i][j]，i代表第一条边长为i，j为第二条边长为j，则第三条边长为c-i-j，判定所有情况。最后验证即可。因为三角形每条边长不可能超过周长的一半，所以枚举i,j最大到c/2即可。最后注意结果小数部分不是四舍五入，而是直接截断的，所以可以利用强制转化。

DP代码：

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<math.h>

using namespace std;

const int N=*;

int f[N][N];

int a[],c=,n;

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++){

        scanf("%d",&a[i]);

        c+=a[i];

    }

    memset(f,,sizeof(f));

    f[][]=;

    for(int i=;i<=n;i++){

        for(int j=c/+;j>=;j--){

            for(int k=c/+;k>=;k--){

                if(j-a[i]>= && f[j-a[i]][k]){

                    f[j][k]=;

                }

                if(k-a[i]>= && f[j][k-a[i]]){

                    f[j][k]=;

                }

            }

        }

    }

    double s=;

    for(int i=c/+;i>=;i--){

        for(int j=c/+;j>=;j--){

            if(f[i][j]){

                double la=i,lb=j,lc=c-i-j;

                double p=(la+lb+lc)/2.0;

                if(sqrt(p*(p-la)*(p-lb)*(p-lc))>s){

                    s=sqrt(p*(p-la)*(p-lb)*(p-lc));

                }

            }

        }

    }

    printf("%d\n",s== ? - : (int)(s*));

    return ;

}

DFS代码：

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<math.h>

using namespace std;

const int N=;

int n,sum,la=,lb=,c=,lc;

int a[N],f[N];

double s=;

void dfs(int k)

{

    if(la>c/ || lb>c/ || lc>c/) return ;

    if(k==n){

        if(la+lb>lc && la+lc>lb && lb+lc>la){

            double p=(la+lb+lc)/2.0;

            if(sqrt(p*(p-la)*(p-lb)*(p-lc))>s){

                s=sqrt(p*(p-la)*(p-lb)*(p-lc));

            }

        }

        return ;

    }

    for(int i=;i<n;i++){

            if(!f[i])

            for(int j=;j<;j++){

                if(j==){

                    la+=a[i];

                    f[i]=;

                    dfs(k+);

                    f[i]=;

                    la-=a[i];

                }

                if(j==){

                    lb+=a[i];

                    f[i]=;

                    dfs(k+);

                    f[i]=;

                    lb-=a[i];

                }

                if(j==){

                    lc+=a[i];

                    f[i]=;

                    dfs(k+);

                    f[i]=;

                    lc-=a[i];

                }

            }

    }

}

int main()

{

    memset(f,,sizeof(f));

    scanf("%d",&n);

    for(int i=;i<n;i++){

        scanf("%d",&a[i]);

        c+=a[i];

    }

    dfs();

    printf("%d\n",s== ? -:(int)(s*));

    return ;

}

巴特西

[POJ] 1948 Triangular Pastures (DP)

最新文章

热门文章