加载中... 加载中...

【2025 年 5 月月赛赛题 B 题解】小 A 买玩具

chenyuan3

简单的背包。

#include <bits/stdc++.h>
using namespace std;
int n, m, a[4010], dis[10010];
int main()
{
	memset(dis, 0x3f, sizeof dis);
    dis[0] = 0;
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
    {
        cin >> a[i];
    }
	for (int i = 1; i <= n; i++)
    {
		for (int j = 1; j <= m; j++)
        {
			if (i - a[j] >= 0)
            {
                dis[i] = min(dis[i], dis[i - a[j]] + 1);
            }
		}
	}
	cout<<dis[n];
	return 0;
}