虽然知道过不了,但还是求减枝
查看原帖
虽然知道过不了,但还是求减枝
247162
zty1203楼主2022/8/11 10:57

特判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;
}
2022/8/11 10:57
加载中...