记录链接

代码：

# include <bits/stdc++.h>

# define old_six \
	ios::sync_with_stdio (0);\
	\
	cin.tie (0);\
	\
	cout.tie (0);

# define ffor(i,name) \
	for (auto i = name.begin (); i != name.end (); ++ i)

# define iter(type) \
	type :: iterator

# define reg register

# define inl inline

using namespace std;

typedef long long ll;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

int k, n, ans, a[55], dp[2000005];

int main () {

	old_six

	cin >> k >> n;

	fill (dp + 1, dp + 2000005, 1e9);

	for (reg int i = 0; i < n; ++ i)
		cin >> a[i];

	for (reg int i = 0; i < 2000005; ++ i)
		for (reg int j = 0; j < n; ++ j)
			if (i >= a[j] && dp[i - a[j]] < k)
				dp[i] = min (dp[i], dp[i - a[j]] + 1);

	while (dp[ans] <= k)
		++ ans;

	cout << ans - 1;

	return 0;

}

为什么时间这么短？时间复杂度应该是 $O(n\times\max\limits_{i=1}^na_i)$（如果我没算错的话，当然这里的 $\max\limits_{i=1}^na_i$ 已经变成了一个常数，为 $2\times10^6$），按一秒运算 $10^8$ 来算，那么在大数据（$n$ 到达 $50$）面前会到达一秒鸭，是洛谷又双叒叕在吸氧了还是数据太水了？