历史记录

10.20 感谢whx大佬指正，题解代码已更新
11.05 更新树状数组std

LIS加01背包

设\(f_{i, j}\)为前\(i\)个数中背包为\(j\)时的最长上升子序列的长度，\(w_i, h_i\)分别为第\(i\)个飞机的花费和高度。
则转移方程为\(f_{i, j} = max\{ f_{k, j-w_i} \} - 1\)，\(k\)的取值满足\(k < i, h_k < h_i\)。
边界全是\(0\)，因此实际实现中不需要考虑边界问题。
时间复杂度\(O(n^3)\)，在本OJ提交可以获得20分，在洛谷提交可以获得60分（你谷评测机太强大啦）

#include<bits/stdc++.h>
#define MAXN 3005
using namespace std;
int N, W;
int h[MAXN];
int w[MAXN];
int dp[MAXN][MAXN];
int main(){
    cin>>N>>W;
    for(int i=1;i<=N;i++)
        cin>>h[i]>>w[i],dp[i][w[i]]=1;
    
    for(int i=1;i<=N;i++)
        for(int j=w[i];j<=W;j++)
            for(int k=1; k<i; k++)
                if (h[k] < h[i])
                    dp[i][j] = max(dp[i][j], dp[k][j-w[i]]+1);
    int ans=0;
    for(int i=1;i<=W;i++)
        for(int j=0;j<=N;j++)
            ans=max(ans,dp[j][i]);
    cout<<ans<<endl;
    
    return 0;
}

进一步优化：\(O(nlogn)\) 二分栈或树状数组优化

#include<bits/stdc++.h>
using namespace std;
int lowbit(int x){return x&-x;}
struct Tree{
    int c[100010];
    void add(int x,int val){
        for(int i=x;i<=100010;i+=lowbit(i))
            c[i]=max(c[i],val);
    }
    int ask(int x){
        int ret=0;
        for(int i=x;i;i-=lowbit(i))
            ret=max(ret,c[i]);
        return ret;
    }
}tree[3010];
int h[3010],w[3010];
int main(){
    //  freopen("data.in","r",stdin);
    //  freopen("data.out","w",stdout);
    int N,W;
    scanf("%d%d",&N,&W);
    for(int i=1;i<=N;i++)
        scanf("%d%d",h+i,w+i);
    int ans=0;
    for(int i=1;i<=N;i++)
        for(int j=w[i];j<=W;j++){
            int tmp=tree[j-w[i]].ask(h[i]-1);
            ans=max(ans,tmp+1);
            tree[j].add(h[i],tmp+1);
        }
    printf("%d",ans);
}

感谢whx大佬提供std