AtCoder Beginner Contest 013 C - 節制

線形計画法？

C - 節制

AtCoderの過去問を解いていて気になった問題です。この問題は線形計画問題に似ていると思います。

実行可能領域に端点がない？ので、境界に近い格子点を調べる必要があります。解説を見て解答作ったんですが、1つの変数を固定すれば残りの変数も自動的に決まるわな。

線形計画問題といえばシンプレックス法が有名ですが、もう覚えてないですね。シンプレックス法を使った問題とか出てきそうな予感がします。

コード

import java.util.Scanner;

public class ProblemC {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        long N = scan.nextLong();
        long H = scan.nextLong();
        long A = scan.nextLong();
        long B = scan.nextLong();
        long C = scan.nextLong();
        long D = scan.nextLong();
        long E = scan.nextLong();
        scan.close();


        if(H - N * E > 0) {
            System.out.println(0);
            System.exit(0);
        }


        long ans = N * A;
        for(long i = 0; i <= N; i++) {
            long x = i;
            double y1 = (double)(N * E - H -(B + E) * x) / (D + E);
            long y;
            if(y1 < 0) {
                y = 0;
            }else {
                y = (N * E - H -(B + E) * x) / (D + E) + 1;
            }
            long t = A * x + C * y;
            if(ans > t) {
                ans = t;
            }
        }
        System.out.println(ans);
    }
}

参考サイト

下のサイトの解説が良くまとまっていました。 wk1080id.hatenablog.com