90分dp求助,第四个测试点错误
查看原帖
90分dp求助,第四个测试点错误
46534
Y_Dream楼主2020/10/12 14:04

采用按数值排序,从小到大依次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;
}
2020/10/12 14:04
加载中...