小红走矩阵 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]; }