evil______ 2022-03-08 17:20 采纳率: 55.6%
浏览 236
已结题

试题 算法提高 网格贪吃蛇

问题描述
  那个曾经风靡全球的贪吃蛇游戏又回来啦!这次贪吃蛇在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;
    
} 

img


错了个点,有哪位同学帮忙看下,或者有其他的思路方法。要是有蓝桥杯的vip能不能帮忙看下数据谢谢

  • 写回答

1条回答 默认 最新

  • 於黾 2022-03-08 17:31
    关注

    我觉得你思路好像有问题啊,为什么是找最长递增序列
    你不应该先把豆撒进二维数组里,然后递归吗
    你找最长递增序列,那有2个点,(2,7)和(8,2),你吃完(2,7)还能取吃(8,2)吗,违反规则了呀

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 10月26日
  • 已采纳回答 10月18日
  • 创建了问题 3月8日

悬赏问题

  • ¥200 如何使用postGis实现最短领规划?
  • ¥15 pyinstaller打包错误
  • ¥20 cesm的气溶胶排放文件
  • ¥15 逐月累计,月份不连续,补齐月份
  • ¥15 应用简单的Python代码完成一个学生成绩管理系统
  • ¥15 用matlab求微分方程初值问题
  • ¥15 vscode下编写第三方库opencv与pcl代码时没有代码提示
  • ¥15 能够跑通不报错,如何解决?(标签-matlab)
  • ¥15 MOS在RDS较大,频率高时开关波形异常
  • ¥15 SCENIC分析报错求解答