yukicoder No.247 線形計画問題もどき
これはもっと早く解けるべきだった…
解法
dp[c] = 「cを作るx_1, ..., x_nの組の最小値」
とするとdpで解ける。
const int MAXC = 100100; const int MAXN = 101; const int INF = 1e9; int dp[MAXC]; int C, N; int a[MAXN]; int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> C; cin >> N; for (int i = 1; i <= N; i++) { cin >> a[i]; } for (int i = 1; i <= C; i++) dp[i] = INF; for (int i = 1; i <= N; i++) { for (int j = 0; j < C; j++) { if (dp[j] < INF) { if (j+a[i] <= C) dp[j+a[i]] = min(dp[j+a[i]], 1+dp[j]); } } } int ans = dp[C]; if (ans == INF) ans = -1; cout << ans << endl; return 0; }