求助!就过了三个,咋回事啊

P1434 [SHOI2002] 滑雪

207394848R @ 2022-06-06 11:10:58

#include <iostream>
#include <string.h>
#include<cstdio>
#include<cctype>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<climits>
#include<map>
#include<queue>
using namespace std;

const int maxn = 100 + 10;

int towards[4][2] = {
    {1,0},{-1,0},{0,1},{0,-1}
};

struct Node{
    int x, y;
    int height;
}orders[maxn * maxn];

bool cmp(Node a, Node b)
{
    return a.height < b.height;
}
int n, m, nums[maxn][maxn], numsCopy[maxn][maxn], maxnum, steps[maxn][maxn], maxStep = 0;

int main()
{
    fill(steps[0], steps[0] + maxn * maxn, 1);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> nums[i][j];
            numsCopy[i][j] = nums[i][j];
            orders[m * i + j].height = nums[i][j];
            orders[m * i + j].x = i;
            orders[m * i + j].y = j;
        }
    }
    /*for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            printf("%d    (%d,%d,%d)\n", nums[i][j], orders[m * i + j].x, orders[m * i + j].y, orders[m * i + j].height);
        }
    }*/
    sort(orders, orders + n * m, cmp);
    /*for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            printf("(%d,%d,%d)\n", orders[m * i + j].x, orders[m * i + j].y, orders[m * i + j].height);
        }
    }*/
    maxnum = orders[0].height;
    for (int i = 0; i < n*m; i++)
    {
        Node newNode;
        for (int j = 0; j < 4; j++)
        {
            //cout << towards[i][0] << "    " << towards[i][1];
            newNode.x = orders[i].x + towards[j][0];
            newNode.y = orders[i].y + towards[j][1];
            newNode.height = numsCopy[newNode.x][newNode.y] + nums[orders[i].x][orders[i].y];
            if (numsCopy[newNode.x][newNode.y] < orders[i].height)
            {
                continue;
            }
            if (newNode.x >= 0 && newNode.x < m &&
                newNode.y >= 0 && newNode.y < n)
            {
                if (newNode.height>nums[newNode.x][newNode.y])
                {
                    nums[newNode.x][newNode.y] = newNode.height;
                    steps[newNode.x][newNode.y] = steps[orders[i].x][orders[i].y] + 1;
                    if (nums[newNode.x][newNode.y] >maxnum)
                    {
                        maxnum = nums[newNode.x][newNode.y];
                    }
                }
                else
                {
                    continue;
                }
            }
            else
            {
                continue;
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (nums[i][j]==maxnum)
            {
                cout << steps[i][j];

            }
        }
    }
    return 0;
}```cpp

我的想法是用一个数组按高度从小到大排序order,再按那个顺序,把点的高度向周围更高的扩散nums。最后得到最高的高度maxnum。因为没看清输出,步数steps后加的应该没问题啊

by IamYoung2021 @ 2022-07-02 11:38:24

建议使用记忆化搜索

还有,你是TLE了,还是WA了?


|