yukicoder No.385 - カップ麺生活
解法
最初に個数制限なしナップザックを解いて, ある金額を使った時買える最大のカップラーメンの個数を求めておきます.
その後残金が素数になるようなすべての使い方を行い, 最後に最も多くカップラーメンを買えるような使い方をすればよいです.
ソースコード
#include <iostream> #include <cstring> using namespace std; const int kMAX_M = 10010; const int kMAX_N = 30; int M, N; int C[kMAX_N]; int can_adjust[kMAX_M]; bool IsPrime(int num) { if (num == 0 || num == 1) return false; for (int i = 2; i * i <= num; i++) { if (num % i == 0) return false; } return true; } void Solve() { memset(can_adjust, -1, sizeof(can_adjust)); can_adjust[0] = 0; // 個数制限なしナップザック for (int i = 0; i < N; i++) { for (int price = 0; price <= M; price++) { if (price - C[i] >= 0 && can_adjust[price - C[i]] >= 0) { can_adjust[price] = max(can_adjust[price], can_adjust[price - C[i]] + 1); } } } int answer = 0, max_num = 0; for (int price = 0; price <= M; price++) { int remaining = M - price; if (IsPrime(remaining) && can_adjust[price] > 0) { answer += can_adjust[price]; } max_num = max(max_num, can_adjust[price]); } answer += max_num; cout << answer << endl; } int main() { cin >> M >> N; for (int i = 0; i < N; i++) { cin >> C[i]; } Solve(); return 0; }