aoj 0567 - Best Pizza
問題概要
条件に合う最もよいピザを選ぶ
解法
この問題は貪欲法で解ける。なぜなら、トッピングの値段がすべて同じだからである。トッピングの値段が同じであるなら、トッピングのカロリーが高いものから優先的に選んでいけばいい。あとは、何個のトッピングを選ぶ時が最適解なのかわからないので、それを全探索すればいい。トッピングを選ぶ数を0~n個として、カロリーの高いものから順に選んですべての場合の カロリー/値段を計算して一番大きいものを答えとして出力すればいい。
ミス
dp臭がすごかった。たぶんdpでもできるのでdpで解きたい。
コード
#include <iostream> #include <algorithm> #include <vector> #include <cstdio> #include <cmath> using namespace std; #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) //貪欲法で解ける int main(void){ int n, a, b; double kizi; cin >> n >> a >> b >> kizi; vector<int> debu(n + 1);//カロリーを入れる配列 rep(i, n) cin >> debu[i]; sort(debu.begin(), debu.end()); reverse(debu.begin(), debu.end());//大きいものから並べる vector<double> ans(n + 1); //カロリーが高いものから優先的に選んでいく rep(i, n + 1){//i個のトッピングを選ぶとき double nedan = (double)a + (double)i * (double)b;//値段の計算 double karori = kizi;//生地のカロリーを初期値とする rep(j, i) karori += debu[j];//i個のトッピングをカロリーの高いものから優先的にi個選んでいる ans[i] = karori / nedan;//答えを入れておく } sort(ans.begin(), ans.end()); reverse(ans.begin(), ans.end()); printf("%d\n", (int)floor(ans[0]));//一番大きいものを出力 return 0; }