问题描述
那个曾经风靡全球的贪吃蛇游戏又回来啦！这次贪吃蛇在m行n列的网格上沿格线爬行，从左下角坐标为(0,0)的格点出发，在每个格点处只能向上或者向右爬行，爬到右上角坐标为(m-1,n-1)的格点时结束游戏。网格上指定的格点处有贪吃蛇喜欢吃的豆豆，给定网格信息，请你计算贪吃蛇最多可以吃多少个豆豆。
输入格式
输入数据的第一行为两个整数m、n（用空格隔开），分别代表网格的行数和列数；第二行为一个整数k，代表网格上豆豆的个数；第三行至第k+2行是k个豆豆的横纵坐标x、y（用空格隔开）。
输出格式
程序输出一行，为贪吃蛇可吃豆豆的最大数量。
样例输入
10 10
10
3 0
1 5
4 0
2 5
3 4
6 5
8 6
2 6
6 7
3 1
样例输出
5
数据规模和约定
1≤m, n≤10^6，0≤x≤m-1，0≤y≤n-1，1≤k≤1000
#include<stdio.h>
int n,m,k;
int x[3][10000];
int dp[2000000];
int mark[1000000];
int max=0;
int main(){
int i,j;
scanf("%d",&m);
scanf("%d",&n);
scanf("%d",&k);
for(i=0;i<k;i++){
scanf("%d",&x[1][i]);
scanf("%d",&x[2][i]);
}
//堆排序先对行排序因为肯定是从小的行往上面大的行走
int heapSize=k;
for(i=0;i<k;i++){
int middle=i;
while(x[1][middle]>x[1][(middle-1)/2]){
x[1][middle]^=x[1][(middle-1)/2];
x[1][(middle-1)/2]^=x[1][middle];
x[1][middle]^=x[1][(middle-1)/2];
x[2][middle]^=x[2][(middle-1)/2];
x[2][(middle-1)/2]^=x[2][middle];
x[2][middle]^=x[2][(middle-1)/2];
middle=(middle-1)/2;
}
}
if(k==0){
printf("0");
return 0;
}
while(--heapSize){
x[1][heapSize]^=x[1][0];
x[1][0]^=x[1][heapSize];
x[1][heapSize]^=x[1][0];
x[2][heapSize]^=x[2][0];
x[2][0]^=x[2][heapSize];
x[2][heapSize]^=x[2][0];
int index=0;
while(2*index+1<heapSize){
int largest=2*index+2<heapSize&&x[1][2*index+2]>x[1][2*index+1]?(2*index+2):(2*index+1);
if(x[1][largest]>x[1][index]){
x[1][largest]^=x[1][index];
x[1][index]^=x[1][largest];
x[1][largest]^=x[1][index];
x[2][largest]^=x[2][index];
x[2][index]^=x[2][largest];
x[2][largest]^=x[2][index];
index=largest;
}
else if(x[1][largest]==x[1][index]&&x[2][largest]>x[2][index]){
x[2][largest]^=x[2][index];
x[2][index]^=x[2][largest];
x[2][largest]^=x[2][index];
index=largest;
}
else break;
}
}
//对行排完序后又因为是向右走所以变成了在排完序的基础上找最长递增序列然后输出它的长度
for(i=0;i<k;i++)mark[i]=1;
for(i=0;i<k;i++){
for(j=0;j<i;j++){
if(x[2][i]>=x[2][j]){
mark[i]=mark[j]+1>mark[i]?mark[j]+1:mark[i];
}
}
if(mark[i]>max)max=mark[i];
}
printf("%d",max);
return 0;
}
错了个点，有哪位同学帮忙看下，或者有其他的思路方法。要是有蓝桥杯的vip能不能帮忙看下数据谢谢
