90分dp求助,第四个测试点错误

P1434 [SHOI2002] 滑雪

Y_Dream @ 2020-10-12 14:04:39

采用按数值排序,从小到大依次dp的方法。dp[i][j]表示从i,j出发可以滑雪的最大距离。它可从四个来源点转移过来。代码如下。

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,y,v;
}p[10010];
int r,c,a[110][110],dp[110][110],ans;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
bool cmp(node m,node n)
{
    return m.v<n.v;
}
int main()
{
    cin>>r>>c;
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
        {
            cin>>a[i][j];
            dp[i][j]=1;
            p[(i-1)*c+j]={i,j,a[i][j]};
        }
   sort(p+1,p+r*c+1,cmp);
    for(int i=2;i<=r*c;i++)
    {
        for(int j=0;j<4;j++)
        {
            int nx=p[i].x+dx[j];
            int ny=p[i].y+dy[j];
            if(a[nx][ny]<p[i].v && nx>0 && nx<=r && ny<=c && ny>0)
                dp[p[i].x][p[i].y]=max(dp[p[i].x][p[i].y],dp[nx][ny]+1);
        }
        ans=max(ans,dp[p[i].x][p[i].y]);
    }
    cout<<ans<<endl;
    return 0;
}

by Y_Dream @ 2020-10-12 14:43:32

过掉了,怀疑第四个点为全0的点。应该输出1。 源程序结果为0。


|