AcWing 165. 小猫爬山
原题链接
简单
作者:
小.bug
,
2022-05-16 21:18:59
,
所有人可见
,
阅读 145
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int a[N];
int used[N];
int n, m;
int res = N;
void dfs(int u, int cnt)
{
if(cnt >= res) return;
if(u > n)
{
res = cnt;
return;
}
//看看能不能坐原来的车
for(int i = 0; i < cnt; i++)
{
if(m - used[i] >= a[u])
{
used[i] += a[u];
dfs(u+1,cnt);
used[i] -= a[u];
}
}
//开一辆新车
used[cnt] += a[u];
dfs(u + 1,cnt + 1);
used[cnt] -= a[u];
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
dfs(1,0);
cout << res << endl;
return 0;
}