本文共 1689 字,大约阅读时间需要 5 分钟。
题目:
题目大意:
给N条边,把这些边组成一个三角形,问面积最大是多少?必须把所有边都用上。
思路:
对于已知周长的三角形,我们只要知道两条边的长度变可推出第三条边,所以可以得到状态方程:
f[i][j][k] 表示用前i条边,能否组成长度为j和k的两条边 初始化f[0][0][0] = true; f[i][j][k] = f[i-1][j-len[i]][k] || f[i-1][j][k-len[i]]; 如果f[i][j][k]=true,那么就计算以j,k,sum-j-k为三条边能否组成三角形,如果可以就用海伦公式计算面积。 由于如果要开三维数组的话,要开f[40][1600][1600],明显是要MLE的,所以要降成二维的, 而时间复杂度40*1600*1600,如果没有优化直接上,是要TLE的。 所以要优化,根据优化的程度,运行时间可以再100MS~1000MS之间:1. f[i][j] 和 f[j][i]是相同的两个三角形,所以递推时可以让 j>=i
2. 对于每条边,一定是小于周长的一半 3. 枚举到第i条边时, 前i条边不可能组成大于等于sum[i] (sum[i]=len[1]+...+len[i])的长度优化了一下时间到了100MS+
代码:
#include#include #include #include #include #include #define SQ(x) ((x)*(x))#define MP make_pairconst int INF = 0x3f3f3f3f;const double PI = acos(-1.0);typedef long long int64;using namespace std;const int MAXN = 42;int n, m;int len[MAXN], sum[MAXN];bool f[1602][1602];inline bool isTriangle(double e[3]){ if(e[2] < e[1]){ swap(e[2], e[1]); if(e[1] < e[0]) swap(e[0], e[1]); } return e[0]+e[1] > e[2];}inline double getArea(double e[3]){ if(!isTriangle(e)) return -1; double p = sum[n]/2.0; return sqrt(p*(p-e[0])*(p-e[1])*(p-e[2]));}int main(){ scanf("%d", &n); for(int i=1; i<=n; ++i){ scanf("%d", &len[i]); sum[i] = sum[i-1]+len[i]; } memset(f, 0, sizeof(f)); f[0][0] = true; double ans = -1; double e[3]; for(int i=1; i<=n; ++i){ for(int v1=min(sum[i],sum[n]>>1); v1>=0; --v1){ for(int v2=min(sum[i]-v1,sum[n]>>1); v2>=v1; --v2)if(v1+v2 = 0 && f[v1-len[i]][v2]){ f[v1][v2] = true; } if(!f[v1][v2] && v2-len[i]>=0 && f[v1][v2-len[i]]){ f[v1][v2] = true; } if(f[v1][v2]){ ans = max(ans, getArea(e)); } } } } if(ans < 0) puts("-1"); else printf("%d\n", (int)(100*ans)); return 0;}
转载地址:http://rpzni.baihongyu.com/