最长上升子序列(40pts)

• 当$k=0$的时候，就是一个最长上升子序列模型

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
#define x first
#define y second
const int N=510;
PII a[N];
int f[N]; //f[i] 表示以第i个点结尾的上升点列的最大数目
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].x>>a[i].y;
    }
    int res=0;
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
    {
        f[i]=1;
        for(int j=1;j<n;j++)
        {
            if(a[i].x==a[j].x+1&&a[i].y==a[j].y||a[i].x==a[j].x&&a[i].y==a[j].y+1) //可以拼接
            {
                f[i]=f[j]+1;
            }
        }
        res=max(res,f[i]); //更新最大值
    }
    cout<<res;
    return 0;
}

动态规划($O(100n^2)$100pts)

• 使用$f[i][j]$表示以$a[i]$结尾，且在$i$前面插入了j个点的最大长度

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
#define x first
#define y second
const int N=510,M=110;
PII a[N];
int f[N][M]; //f[i][k] 表示在i前面已经插了k个点且以第i个点结尾的上升点列的最大数目
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].x>>a[i].y;
    }
    sort(a+1,a+n+1);
    int res=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=k;j++) //直接插入
        {
            f[i][j]=j+1;
        }
        for(int j=1;j<i;j++) //枚举前面的点
        {
            if(a[j].y>a[i].y) continue;
            
            int d=a[i].x-a[j].x+a[i].y-a[j].y-1; //需要增加d个点
            for(int l=d;l<=k;l++) //枚举不同的状态转移
            {
                f[i][l]=max(f[i][l],f[j][l-d]+d+1);
            }
        }
        res=max(res,f[i][k]); //更新答案
    }
    cout<<res;
    return 0;
}

floyd($On^3 100pts$)

• dist[i][j]=k表示点$i$到点$j$需要插入k个点可以构成上升点列。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
#define x first
#define y second
const int N=510;
PII a[N];  
int n;
int dist[N][N];
int get(PII a,PII b) //得到a到b的曼哈顿距离
{
    return abs(a.x-b.x)+abs(a.y-b.y);
}
void floyd()
{
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
            }
        }
    }
}
int main()
{
    int k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].x>>a[i].y;
    }
    //初始化距离
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i!=j&&a[i].x<=a[j].x&&a[i].y<=a[j].y) 
            {
                dist[i][j]=get(a[i],a[j])-1;
            }
            else
            {
                dist[i][j]=1e9;
            }
        }
    }
    floyd(); //求两个点之间最少添加的点的数目
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(dist[i][j]<=k) //可以填
            {
                ans=max(ans,get(a[i],a[j])+1+k-dist[i][j]); //更新最大距离
            }
        }
    }
    cout<<ans;
    return 0;
}