POJ1948 Triangular Pastures

POJ1948 Triangular Pastures

 1 #include <iostream>
 2 #include <cmath>
 3 using namespace std;
 4 const int maxn = 805;
 5 bool dp[maxn][maxn];
 6 int a[maxn];
 7 double area(double a, double b, double c) {
 8     double p = (a+b+c)/2;
 9     return sqrt(p*(p-a)*(p-b)*(p-c));
10 }
11 bool is_ok(int a, int b, int c) {
12     if (a+b <= c || a+c <= b || b+c <= a)
13         return false;
14     return true;
15 }
16 int main() {
17     int n; cin >> n;
18     int sum = 0;
19     for (int i = 0; i < n; i++) {
20         cin >> a[i];
21         sum += a[i];
22     }
23     dp[0][0] = true;
24     for (int i = 0; i < n; i++) {
25         for (int k = 800; k >= 0; k--) {
26             for (int j = k; j >= 0; j--) {
27                 if (k-a[i] >= 0 && dp[k-a[i]][j])
28                     dp[k][j] = true;
29                 if (j-a[i] >= 0 && dp[k][j-a[i]])
30                     dp[k][j] = true;
31             }
32         }
33     }
34
35     double ans = 0;
36     for (int i = 0; i <= 800; i++) {
37         for (int j = 0; j <= i; j++) {
38             if (dp[i][j] && is_ok(i,j,sum-i-j))
39                 ans = max(ans,100*area(i,j,sum-i-j));
40         }
41     }
42     if (ans == 0) cout << -1 << endl;
43     else cout << (int)ans << endl;
44     return 0;
45 }