Algoogle

Algorithm for Programming Contest

PKU 1948 Triangular Pastures

Category: PKU Tag: dp

Triangular Pastures

問題概要


解法


dp[i][j] := 長さ i と長さ j の辺を作れるかどうか
可能なやつの i, jの片方にまだ使ってないやつ一つの長さを足したやつも可能になる.
頭悪いのでDPの更新順を昇順にしてました.
昇順に更新すると同じやつ複数回使える場合が出てきてしまう.
ナップザックとかと同じように考えれば当然ですね.
あとacosやらsinやらのせいでeps付けないと変な答えがでる場合がある気がする(付けなくても通ったけど).
4 5 3で計算すると599とかになるけど3 4 5なら600で平気だし問題ないのかなあ.

追記:
ヘロンの公式使いましょう.
常識的に考えてそうですよねーということでコード変えました.

コード


(1948.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <algorithm>
#include <cmath>
#include <cstdio>

using namespace std;

const double eps = 1e-8;

inline bool isTri(int i, int j, int k){ return (i + j > k) && (j + k > i) && (k + i > j);}

inline double area(int i, int j, int k){
    double s = 1. * (i + j + k) / 2;
    return sqrt(s*(s-i)*(s-j)*(s-k));
}
int N, L[64], sum;
bool dp[2048][2048];

int main(){
    scanf("%d", &N);
    for(int i = 0; i < N; i++) scanf("%d", L+i);

    dp[0][0] = 1;
    for(int i = 0; i < N; i++){
        for(int j = sum; j >= 0; j--)
            for(int k = sum - j; k >= 0; k--){
                dp[j][k+L[i]] |= dp[j][k];
                dp[j+L[i]][k] |= dp[j][k];
            }
        sum += L[i];
    }

    int ans = -1;
    for(int i = 1; i < sum; i++)
        for(int j = i; i + j < sum; j++)
            if(dp[i][j]) {
                int k = sum - i - j;
                if(isTri(i, j, k)) ans = max(ans, int(100 * area(i, j, k)));
            }

    printf("%d\n", ans);
    return 0;
}

Comments