こちらではpaiza事務局側で作成した模範解答を掲載していす。
C++: paiza事務局作成コード Vol.2 動的計画法
得点:100点
通過テストケース:7/7
#include <algorithm> #include <cstdio> #include <iostream> #include <vector> using namespace std; int main() { int M, N; cin >> M >> N; vector<int> qs(M), rs(N); int sumq = 0, sumr = 0; for(int i = 0; i < N; i++) { cin >> qs[i] >> rs[i]; sumq += qs[i]; sumr += rs[i]; } int m = sumq - M; vector<int> dp(m + 1, 0); for(int i = 0; i < N; i++) { int q = qs[i], r = rs[i]; for (int j = m; j >= q; j--) dp[j] = max(dp[j], dp[j - q] + r); } cout << sumr - dp[m] << endl; return 0; }
C++: paiza事務局作成コード Vol.1 O(2^n)
得点:71点
通過テストケース:5/7
#include <algorithm> #include <cstdio> #include <iostream> #include <vector> #include <cmath> using namespace std; int main() { int M, N; cin >> M >> N; vector<int> qs(N), rs(N); for(int i = 0; i < N; i++) { cin >> qs[i] >> rs[i]; } //m社のうちi番目の会社を使うか使わないかの表を作る //3社とかなら // A, B, C // 1, 1, 1 // 1, 1, 0 // 1, 0, 1 //.....続く... //みたいな1を使う0は使わないの表を作る vector< vector<int> > use_list (pow(2,N), vector<int>(N) ); for (int i = 0; i < (1<< N); i++) { for (int j = 0; j < N; j++) { use_list[i][j] = (i>>j&1); } } //使う使わないリストから、人月を満たせる組み合わせで最安を探す int ans = 0; for (int i = 0; i < N; i++){ ans += rs[i]; } int ningetsu = 0; int cost = 0; for (int i = 0; i < (1<<N); i++){ cost = 0; ningetsu = 0; for (int j = 0; j < N; j++){ if (use_list[i][j] == 1){ ningetsu += qs[j]; cost += rs[j]; } } if (ningetsu >= M && ans > cost){ ans = cost; } } cout << ans << endl; }