C.Sugar Water

問題文

C - Sugar Water

解説

・2種類の水・砂糖しか使えないため、これらを用いて構成できる水・砂糖の組み合わせを考えないと行けない　→　動的計画法
・次に、ある水の量 について考える。このとき、に溶ける砂糖の最大値が求まれば良い。この砂糖の最大値とは、の2つの砂糖を用いて構成される。
・以上より、構成できる水の量を動的計画法で列挙しつつ、その各水の量について砂糖の量を動的計画法で探索すれば良い。
・ gの水でgの塩を溶かせるかどうかの配列。

感想

gの水のときに溶ける最大の砂糖の量

というふうにdpをすると死ぬ。あえて最大まで溶かさずに水を加えることで、濃度を最大化できる場合が存在する（たぶん）

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
constexpr int inf  = 1e8;
int water_ub(int A, int B, int F) {
    return (F/(100)) *  100;
}
int main(){
    int A,B,C,D,E,F;
    cin >> A >> B >> C >> D >> E >> F;
    int w_ub = water_ub(A,B,F);
    vector<vector<bool>>dp(w_ub + 1,vector<bool>(F,false));
    dp[0][0] = true;
    for(int i = 0; i < dp.size(); ++i){
        for(int j = 0; j < dp[i].size(); ++j){
            bool valid  = dp[i][j];
            if(not valid ) continue;
            if(i + A < dp.size())
                dp[i + A][j] = true;
            if(i + B < dp.size())
                dp[i + B][j] = true;
            if(j + C < dp[i].size() && i * 100 + j + C <= F && 100 * (j + C) <= E * i * 100)
                dp[i][j + C] = true;
            if(j + D < dp[i].size() && i * 100 + j + D <= F && 100 * (j + D) <= E * i * 100)
                dp[i][j + D] = true;
        }
    }
    pair<int,int>ans = {A*100,0};
    for(int i = 0; i < dp.size(); ++i){
        for(int j = 0 ; j < dp[i].size(); ++j){
            if(not dp[i][j]) continue;
            if((ans.second) * (i * 100  + j) < (j) * (ans.first))
                ans = {i * 100 + j,j};
        }
    }
    cout << ans.first << " " << ans.second << endl;
}