小红走矩阵 dp应该可行

https://ac.nowcoder.com/acm/contest/86034/E

第一次交的时候只的了175分。赛后我想了好久,原因是dp是按顺序更新权值,而每个点可以绕远路(远的地方权值还不是最优的),所以更新一次dp不够,再加个for循环多次更新dp数组就可以ac了。如有误请指正

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstring>
#include<vector>
#include<new>
using namespace std;
int A[600][600];
int ans;
int dp[600][600];//对应矩阵的最小路径权值
int main()
{int n;
int p=0;
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
	cin>>A[i][j];
	p=max(p,A[i][j]);
}

for(int i=1;i<=n;i++){
	for(int j=1;j<=n;j++)
	{
		dp[i][j]=p+1;
	}
	
}
 
for(int p=1;p<n;p++){
for(int i=1;i<=n;i++){
	for(int j=1;j<=n;j++)
	{if(i==1&&j==1){dp[1][1]=A[1][1]; continue;}
	if(i>=2)dp[i][j]=min(dp[i][j],dp[i-1][j]);
if(i<=n-1)	dp[i][j]=min(dp[i][j],dp[i+1][j]);	
		if(j>=2)dp[i][j]=min(dp[i][j],dp[i][j-1]);
if(j<=n-1)	dp[i][j]=min(dp[i][j],dp[i][j+1]);	
	dp[i][j]=max(A[i][j],dp[i][j]);
	}
	
}
}
cout<<dp[n][n];
}

全部评论
这样做不对,下面这个数据就过不了。除非p的循环次数改成n^2(绕路的最多次数),这样就超时了 9 1 4 1 1 1 4 1 1 1  1 4 1 4 1 4 1 4 1  1 4 1 4 1 4 1 4 1  1 4 1 4 1 4 1 4 1  1 4 1 4 1 4 1 4 1  1 4 1 4 1 4 1 4 1  1 4 1 4 1 4 1 4 1  1 4 1 4 1 4 1 4 1  1 1 1 4 1 1 1 4 1 如果从左上往右下更新,第一次得到的是走2*n-1步到终点的结果,第二次更新得到的是最多走2*n+1步到终点的结果,每次更新只能得到比上一次多走两步(往上或者往左走一步再回去,共两步)的结果(只有从右边和下边更新数据的时候才会多走一步,从dp左上往右下更新,当前循环中从右边或者下边更新数据都是上一次循环的结果,每次循环只会比上次多一步),感觉这题就不是个线性的dp,得用搜索做
3 回复 分享
发布于 2024-07-15 00:26 北京
麻了
点赞 回复 分享
发布于 2024-07-14 22:04 广东

相关推荐

不愿透露姓名的神秘牛友
07-24 13:35
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务