nylsp @ 2019-01-02 23:23:14
我这样子写之后该怎么优化QAQ
#include<iostream>
using namespace std;
int xi[5005],yi[5005];
int num=0,maxN=0;
int n,a,s,b;
void dfs(int initial)
{
for(int i=initial;i<n;i++)
{
if(a+b<xi[i])
{
if(maxN<num)
maxN=num;
return;
}
else
{
if(s-yi[i]>=0)
{
s-=yi[i];
num++;
dfs(i+1);
s+=yi[i];
num--;
}
}
}
}
int main()
{
cin>>n>>s;
cin>>a>>b;
int i,j;
for(i=0;i<n;i++)
{
cin>>xi[i]>>yi[i];
}
for(i=0;i<n;i++)
{
int min=i;
for(j=i;j<n;j++)
{
if(xi[j]<xi[min])
min=j;
}
if(min!=i)
{
int temp=xi[i];
xi[i]=xi[min];
xi[min]=temp;
temp=yi[i];
yi[i]=yi[min];
yi[min]=temp;
}
}
dfs(0);
cout<<maxN;
return 0;
}
by _stellar @ 2019-01-02 23:26:49
要我告诉他这道题是贪心吗(小声)
by nylsp @ 2019-01-02 23:28:19
@MrWangnacl 所以是对体力排序还是对高度排序啊
by xiangling @ 2019-01-02 23:29:43
这题还是比较明显的...不要一昧想着dfs
by _stellar @ 2019-01-02 23:32:53
@nylsp 按照力气升序排序,依次枚举就行了
by NaCly_Fish @ 2019-01-02 23:33:01
orz 为啥要搜索啊
by Quank123Wip @ 2019-01-03 06:17:12
@MrWangnacl 明明是红黑树板子题
by nylsp @ 2019-01-03 08:20:07
@NaCly_Fish 我看题解第二篇也在用搜索,所以想自己写写看
by _stellar @ 2019-01-03 17:46:25
@Quank123Wip orz红黑树dalao