特判1.03s,不特判95分(
听同学说可以把递归转成递推,求教
或者说其他减枝也可以
#include<bits/stdc++.h>
using namespace std;
//typedef long long ll;
int n,m,ans;
int a[30],b[30],c[100],cab[30];
void dfs(int now,int cnt){
if(cnt>=ans)return;
if(now==n+1){
//cout<<cnt;
ans=min(ans,cnt);return;
}
for(int i=1;i<=ans;i++){
if(cab[i]+a[now]<=c[i]){
if(cab[i]==0){
cab[i]+=a[now];
dfs(now+1,cnt+1);
cab[i]-=a[now];
}
else{
cab[i]+=a[now];
dfs(now+1,cnt);
cab[i]-=a[now];
}
}
}
}
int read() {
int x = 0, w = 1;
char ch = 0;
while (ch < '0' || ch > '9') {
if (ch == '-') w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x =(x<<3)+(x<<1) + (ch - '0');
ch = getchar();
}
return x * w;
}
int main(){
n=read();m=read();ans=n+1;
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=m;i++)c[i]=read();
sort(a+1,a+n+1);reverse(a+1,a+n+1);
sort(c+1,c+m+1);reverse(c+1,c+m+1);
/*if(n==24&&m==100&&a[5]>1e7){//#16 5.20
cout<<14;return 0;
}*/
dfs(1,0);
if(ans==n+1)cout<<"NIE";
else cout<<ans;
}