• 欢迎光临~

P1284 三角形牧场

开发技术 开发技术 2022-10-19 次浏览

题意:给出一组木棍,求这些木棍能拼出的最大三角形。

解:边长固定的情况下,面积最大的三角形是等边三角形。因此题就变成,把木棍分成三堆,其加起来长度之和最相近。解法和其二维问题一样,设dp[i][j][k]为以 i,j,k 为三边的三角形能不能拼出来,显然第三维可以压掉,知道其中两条边就可以算出第三条。每次新加一根木棍进行转移,记得倒着遍历。

代码:

P1284 三角形牧场P1284 三角形牧场
#include <bits/stdc++.h>
using namespace std;
#define maxx 105
#define maxn 25
#define maxm 205
#define ll long long
#define inf 1000000009
#define mod 998244353
int n;
int a[maxx];
int dp[1005][1005]={0};
int check(int a,int b,int c){
    if(a+b>c&&a+c>b&&b+c>a) return 1;
    return 0;
}
double area(double a,double b,double c){
    double p=(a+b+c)/2;
    return sqrt(p*(p-a)*(p-b)*(p-c));
}
signed main(){
//    int T;
//    scanf("%d",&T);
//    while(T--){
//
//    }
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    int sum=0;
    for(int i=1;i<=n;i++)
        sum+=a[i];
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=800;j>=0;j--){
            for(int k=800;k>=0;k--){
                if(j-a[i]>=0&&dp[j-a[i]][k]) dp[j][k]=1;
                if(k-a[i]>=0&&dp[j][k-a[i]]) dp[j][k]=1;
            }
        }
    }
    int ans=-1;
    for(int i=1;i<=800;i++){
        for(int j=1;j<=800;j++){
            if(dp[i][j]&& check(i,j,sum-i-j)){
                ans=max(ans,(int)(area(i,j,sum-i-j)*100));
            }
        }
    }
    printf("%dn",ans);
    return 0;
}
View Code

 

程序员灯塔
转载请注明原文链接:P1284 三角形牧场
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com