Description
Input
Output
Sample Input
5 1 1 3 3 4
Sample Output
692
Hint
题意:给出n条木棍,选择其中一部分拼成三角形,并使得面积最大。
最初的想法设一个四维数组,dp[t][i][j][k],为当前第t个木棍组成的三角形三边的长度分别为i,j,k是否可能存在(可能存在就是可以由边界推得,但不一定满足要求),然后枚举i,j,k确定是否满足题意并更新最大面积。
如果t是逆序枚举,那么第一维可以省略,因为总长已知,知道i,j,那么k也可以算出。所以简化到dp[i][j].可令i>=j.
如果dp[i-a[t]][j]存在或者dp[i][j-a[t]]存在 ,那么dp[i][j]就可能存在,标记为1.
然后遍历dp[][],寻找可能存在的dp[i][j],然后确定是否满足题意并更新答案。
这里为什么要标记之后再遍历,而不是标记之后就直接计算?因为标记之后直接计算可能会出现状态为i或j为0,而且一个状态可能被计算多次。
#include <stdio.h> #include <string.h> #include <algorithm> #include <math.h> using namespace std; typedef long long LL; const int MAX=0x3f3f3f3f; int area(double a,double b,double c) { double s=(a+b+c)/2; return 100*sqrt(s*(s-a)*(s-b)*(s-c)); } int a[45], dp[810][810],n,sum=0; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); sum+=a[i]; } int tmp = sum/2 ,_max=0; dp[0][0]=1; for(int i=1;i<=n;i++) for(int j=tmp;j >= 0;j--) for(int k=j;k >= 0;k--) if( j >= a[i] && dp[ j-a[i] ][k] || k >= a[i] && dp[j][ k-a[i] ] ) dp[j][k] = 1; for(int i=tmp;i>=1;i--) for(int j=i;j>=1;j--) if( dp[i][j] ) { int k=sum-i-j; if( i+k<=j || i+j<=k || j+k<=i ) continue; int ans = area( i,j,k ); if( ans > _max ) _max=ans; } if( _max != 0 ) printf("%d\n",_max); else printf("-1\n"); return 0; }
POJ 1948 Triangular Pastures(DP),布布扣,bubuko.com
POJ 1948 Triangular Pastures(DP)
原文:http://blog.csdn.net/u013923947/article/details/38228083