51nod1339飞行任务

首先按照收获从大到小排序。

然后01背包取或者不取即可。

至于为什么这样对的其实我也不知道。。。。

代码：

#include<bits/stdc++.h>
using namespace std;
int T,n,f;
struct xx
{
    int d,r,val;
}num[100003];
inline bool cmp(xx a,xx b)
{
    if(a.r==b.r)return a.d>b.d;
    return a.r>b.r;
}
int jiyi[53][50003];
int dp(int now,int val)
{
    int &fanhui=jiyi[now][val];
    if(fanhui!=-1)return fanhui;
    if(now==n+1)return fanhui=0;
    fanhui=dp(now+1,val);
    if(val>=num[now].d)
     fanhui=max(dp(now+1,val-num[now].val)+1,fanhui);
    return fanhui;
}
int main()
{
    scanf("%d",&T);
    while(T--)
     {
        memset(jiyi,-1,sizeof(jiyi));
        scanf("%d%d",&n,&f);
        for(int i=1;i<=n;i++) 
         {
            scanf("%d%d",&num[i].d,&num[i].r);
            num[i].val=num[i].d-num[i].r;
          }
        sort(num+1,num+n+1,cmp);
        printf("%d
",dp(1,f));
     }
    return 0;
}