Sugar Water [AtCoder Regular Contest 083 / AtCoder Beginner Contest 074 C]

https://beta.atcoder.jp/contests/arc083/tasks/arc083_a

解説

https://beta.atcoder.jp/contests/arc083/submissions/1604128

全ての砂糖水の状態を考え、濃度が一番高いものを答える。
「rep(i, 1, F + 1) rep(j, 0, i + 1)」でiは水溶液の質量、jはそのうちの砂糖の質量である。
この時、その組み合わせが実現可能かを判定する必要があるが、これはdpを使って実現する。
　
dp[i][j] := 水溶液がiグラム、そのうち砂糖がjグラムである状態にできるか
遷移元のいずれかのdpの値が1であれば、その状態のdpは1になる。
操作1～4についてそれをチェックする。
　
あとは「砂糖が全て解けきっている」かつ「dp[i][j]==1」かつ「砂糖が少しでも溶けている(0

int dp[3030][3030];
int A, B, C, D, E, F;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> A >> B >> C >> D >> E >> F;
 
    double ma = 0;
    int ans1 = 100 * A, ans2 = 0;
    dp[0][0] = 1;
    rep(i, 1, F + 1) rep(j, 0, i + 1) {
        int water = i - j;
        int suger = j;
 
        if (100 * A <= i) if (dp[i - 100 * A][j]) dp[i][j] = 1;
        if (100 * B <= i) if (dp[i - 100 * B][j]) dp[i][j] = 1;
        if (C <= i && C <= j) if (dp[i - C][j - C]) dp[i][j] = 1;
        if (D <= i && D <= j) if (dp[i - D][j - D]) dp[i][j] = 1;
 
        if (suger * 100 <= water * E && dp[i][j] && 0 < j) {
            double e = 1.0 * 100 * j / i;
            if (ma < e) {
                ma = e;
                ans1 = i;
                ans2 = j;
            }
        }
    }
 
    printf("%d %d\n", ans1, ans2);
}