分析：這是一道典型的動(dòng)態(tài)規(guī)劃。遞推公式為：

A[m][n]=???mnmin(A[m?1][n],A[m][n?1])+1(n==1)(m==1)(else)A[m][n]={m(n==1)n(m==1)min(A[m?1][n],A[m][n?1])+1(else)
代碼如下：

#include<iostream> using namespace std; int main(){/*step 1*/int A[1000][1000];for(int i = 1; i<1000; i++){for(int j = 1; j<1000;j++){A[i][j] = 0;}}for(int i=0; i<1000; i++){A[i][0] = i;A[0][i] = i;}/*step 2*/int num_dangerous;cin>>num_dangerous;if(num_dangerous == 0){cout<<0<<endl;//not surereturn 0;}int danger_point[1000][2];int abscissa = 0;int ordinary = 0;for(int i = 0; i < num_dangerous; i++){cin>>danger_point[i][0];danger_point[i][0]--;abscissa = abscissa > danger_point[i][0] ? abscissa : danger_point[i][0];}for(int i = 0; i < num_dangerous; i++){cin>>danger_point[i][1];danger_point[i][1]--;ordinary = ordinary > danger_point[i][1] ? ordinary : danger_point[i][1];}/*step 3*/for(int i = 1; i <= abscissa; i++){for(int j = 1; j <= ordinary; j++){A[i][j] = A[i-1][j] > A[i][j-1] ? A[i][j-1] : A[i-1][j];//minA[i][j]++;}}/*step 4*/int shortest_time = 2000;for(int i = 0 ; i < num_dangerous; i++){shortest_time = shortest_time < A[danger_point[i][0]][danger_point[i][1]] ? shortest_time : A[danger_point[i][0]][danger_point[i][1]];}cout<< shortest_time << endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的解救小易——网易笔试的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。