AcWing 1024 装箱问题
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 200010, mod = 1e9 + 7;
int n, m, k, x, y, z, ans, t;
int w[N], f[N];
void solve()
{
cin >> m >> n;
for (int i = 0; i < n; i ++ )
{
cin >> x;
for (int j = m; j >= x; j -- )
{
f[j] = max(f[j], f[j - x] + x);
}
}
cout << m - f[m];
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
// cin >> T;
while (T -- )
{
solve();
}
}