Miku

很简单的线性dp

或者说不用dp

有两维，随便按照一维降序排个序，就成了个固定顺序的一维问题了。

直接$O(n^2)$贪心划分不下降子序列或者说运用dilworth定理，求最长上升子序列

贪心更快诶，可能是因为continue的多？

dp

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct sti{
    int len;
    int wi;
}miku[5001];
int vis[5001];
int dp[5001];
bool cmp(sti x,sti y){
    return x.len>y.len;
}
int n;
int simex;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d%d",&miku[i].len,&miku[i].wi);
    }
    sort(miku+1,miku+n+1,cmp);
    for(int i=1;i<=n;++i){
        if(vis[i])
        continue;
        vis[i]=1;
        simex++;
        int tem=miku[i].wi;
        for(int j=i+1;j<=n;++j){
            if(vis[j])
            continue;
            if(miku[j].wi<=tem){
                vis[j]++;
                tem=miku[j].wi;
            }
        }
    }
    cout<<simex;
    return 0;
}

贪心

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct sti{
    int len;
    int wi;
}miku[5001];
int vis[5001];
int dp[5001];
bool cmp(sti x,sti y){
    return x.len>y.len;
}
int n;
int simex;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d%d",&miku[i].len,&miku[i].wi);
    }
    sort(miku+1,miku+n+1,cmp);
    for(int i=1;i<=n;++i){
        for(int j=0;j<i;++j){
            if(miku[j].wi<miku[i].wi){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
        simex=max(simex,dp[i]);
    }
    cout<<simex;
    return 0;
}