博客

离散化的步骤：

排序，去重

得到的序列中元素的位置就是离散化后的坐标。

例如(2,5) (1000,500) (1000, 999)

先将所有数字放入数组中并排序去重得到：

2,5,500,999,1000

离散化后的坐标就是

(1,2) (5,3) (5,4)

该题中地图很大，无法开这么大的二维数组。但实际给出的点就1000个点，所以需要进行离散化。

注意，虽然只有1000个点，但却有2000个数，所以N要定到2000以上。

参考文章：

蓝桥杯 试题 算法提高 网格贪吃蛇（C++）

#include<bits/stdc++.h>
using namespace std;
const int N=2010;
int w[N][N],dp[N][N];
typedef pair<int,int> PII;
vector<PII>loc;
vector<int> nums;
int main()
{
    int n,m;
    cin>>n>>m;
    int k;
    cin>>k;
    while(k--)
    {
        int x,y;
        cin>>x>>y;
        loc.push_back(make_pair(x,y));
        nums.push_back(x);
        nums.push_back(y);
    }
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    for(int i=0;i<(int)loc.size();i++)
    {
        PII point=loc[i];
        w[lower_bound(nums.begin(),nums.end(),point.first)-nums.begin()+1][lower_bound(nums.begin(),nums.end(),point.second)-nums.begin()+1]=1;
    }
    for(int i=1;i<=nums.size();i++)
    {
        for(int j=1;j<=nums.size();j++)
        {
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])+w[i][j];
        }
    }
    cout<<dp[nums.size()][nums.size()];
    return 0;
}