用dp做的,请大佬指出我的错误之处

P1434 [SHOI2002] 滑雪

AidenHou @ 2022-12-28 19:21:09

我的提交记录 链接 代码如下:

#include <iostream>
#include <cmath>
//#include <cstring>
//#include <cstdio>
#include <algorithm>
#include <vector>
//#include <numeric>

//#define UC unsigned char
//#define US unsigned short
//#define U unsigned int
//#define ULL unsigned long long
//#define DEBUG

struct Point {
    int r, c, value;
};

bool compare(Point a, Point b)
{
    return a.value < b.value;
}

int main()
{
    using namespace std;

    int r, c;
    cin >> r >> c;
    vector<Point> points(r * c, Point());
    int** dp = new int*[r];
    points.shrink_to_fit();
    for (int i = 0; i < r; i++)
    {
        dp[i] = new int[c];
        for (int j = 0; j < c; j++)
        {
            dp[i][j] = -1;
            cin >> points[i * c + j].value;
            points[i * c + j].r = i;
            points[i * c + j].c = j;
        }
    }
//  printf("%d %d %d\n", points[5].r, points[5].c, points[5].value);

    sort(points.begin(), points.end(), compare);
//  printf("%d %d %d\n", points[r * c - 1].r, points[r * c - 1].c, points[r * c - 1].value);
//  printf("%d\n", points[0].value);
    int up, down, left, right, cr, cc, cmax = -1;
    for (int i = 0; i < r * c; i++)
    {
        cr = points[i].r;
        cc = points[i].c;
        up = cr > 0 ? dp[cr - 1][cc] : -1;
        down = cr < r - 1 ? dp[cr + 1][cc] : -1;
        left = cc > 0 ? dp[cr][cc - 1] : -1;
        right = cc < c - 1 ? dp[cr][cc + 1] : -1;
        dp[cr][cc] = max(
            0, max(
            up, max(
            down, max(
            left,
            right)))
        ) + 1;
        cmax = max(cmax, dp[cr][cc]);
    }

    cout << cmax << endl;

    return 0;
}

|