Aizu Online Judge(AOJ)の過去問から、その提出コードの解答例です。
・問題 "Four Tea"
https://onlinejudge.u-aizu.ac.jp/problems/2960
・4種類のお茶
僕が作成、提出したコードは、以下のとおりです。
Aizu Online Judge in C++ #Volume29 - 2960 : Four Tea
/* Aizu Online Judge in C++ #Volume29 - 2960 : Four Tea https://onlinejudge.u-aizu.ac.jp/problems/2960 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; ll dp[220]; int main(void){ ll n,ans=1e9; cin>>n; vector<ll> p(4),t(4); for(ll i=0;i<4;i++){ cin>>p[i]; } for(ll i=0;i<4;i++){ cin>>t[i]; } for(ll i=1;i<220;i++){ dp[i]=1e9; for(ll j=0;j<4;j++){ if(i-t[j]>=0){ dp[i]=min(dp[i],dp[i-t[j]]+p[j]); } } } for(ll i=n;i<220;i++){ ans=min(ans,dp[i]); } cout<<ans<<endl; return 0; }
設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/