5个WA 看不到评测点 求助

ztyx @ 2024-04-22 18:49:58

#include <bits/stdc++.h>
using namespace std;

struct node
{
    int x,y,h;
};

vector<node> v;

bool cmp(node x,node y)
{
    return x.h<y.h;
}

int dp[105][105],H[105][105];

int dx[5]={0,1,-1,0,0};
int dy[5]={0,0,0,1,-1};

int main()
{
    int r,c;
    cin >> r >> c;
    for(int i=1;i<=r;i++)
    for(int j=1;j<=c;j++)
    {
        node NEW;
        NEW.x=i;
        NEW.y=j;
        cin >> H[i][j];
        NEW.h=H[i][j];
        v.push_back(NEW);
    }

    sort(v.begin(),v.end(),cmp);

    for(int j=0;j<v.size();j++)
    {
        for(int i=1;i<=4;i++)
        {
            if(H[v[j].x][v[j].y]>H[v[j].x+dx[i]][v[j].y+dy[i]])
            {
                dp[v[j].x][v[j].y]=max(dp[v[j].x][v[j].y],dp[v[j].x+dx[i]][v[j].y+dy[i]]+1);
            }

        }
    }

    int maxn=0;

    for(int i=1;i<=r;i++)
    for(int j=1;j<=c;j++)
    {
        maxn=max(maxn,dp[i][j]);
    }

    cout << maxn;

    return 0;
}

by bulopi @ 2024-04-22 19:50:29

@ztyx 代码的错误就出在没有对dp数组和高度数组初始化。

1. 显而易见，每个dp_{i,j}的初始值都应该为1，即每个点在开始的位置就都、有为1的长度，但具体为什么你的代码没有加这个初始化能过几个点呢？具体原因在下面?

2. 在你的dp子中，一个点可能会从边界外的点转移过来，在高度数组未初始化时边界外的点的值为0所以可能导致错误或不合法的转移，所以就使你的代码过了样例。

AC代码如下（球关）：

#include <bits/stdc++.h>
using namespace std;

struct node
{
    int x,y,h;
};

vector<node> v;

bool cmp(node x,node y)
{
    return x.h<y.h;
}

int dp[105][105],H[105][105];

int dx[5]={0,1,-1,0,0};
int dy[5]={0,0,0,1,-1};

int main()
{
    int r,c;
    cin >> r >> c;

    memset(H, 0x3f3f3f3f, sizeof H);
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++)
            dp[i][j] = 1;

    for(int i=1;i<=r;i++)
    for(int j=1;j<=c;j++)
    {
        node NEW;
        NEW.x=i;
        NEW.y=j;
        cin >> H[i][j];
        NEW.h=H[i][j];
        v.push_back(NEW);
    }

    sort(v.begin(),v.end(),cmp);

    for(int j=0;j<v.size();j++)
    {
        for(int i=1;i<=4;i++)
        {
            if(H[v[j].x][v[j].y]>H[v[j].x+dx[i]][v[j].y+dy[i]])
            {
                dp[v[j].x][v[j].y]=max(dp[v[j].x][v[j].y],dp[v[j].x+dx[i]][v[j].y+dy[i]]+1);
            }

        }
    }

    int maxn=0;

    for(int i=1;i<=r;i++)
    for(int j=1;j<=c;j++)
    {
        maxn=max(maxn,dp[i][j]);
    }

    cout << maxn;

    return 0;
}

by ztyx @ 2024-04-22 21:45:58

@bulopi 好的 谢谢啦