輸入輸出樣例

示例 1

輸入

3 5 -4 -5 -10 -3 1 7 5 -9 3 -10 10 -2 6 -10 -4

輸出

15

運行限制

• 最大運行時間：1s
• 最大運行內存: 128M

這題是很典型的dp問題。畫圖可知，一個點可以到達以它為頂點的一個等腰直角三角形的區域位置，長這樣：

?其中圓圈是出發點，方形是可以走到的點

那么一個點可以從哪里來呢？容易想到是這樣的：

所以對每個點，我們的任務是挑選出上圖中圓圈里邊的最大值，然后與當前的值相加就好了，自底向上的代碼實現如下所示：

#include <bits/stdc++.h> using namespace std; int dx[]={0,0,0,-1,-1,-1,-2,-2,-3}; int dy[]={-1,-2,-3,0,-1,-2,0,-1,0};int main() {// 請在此輸入您的代碼int n,m;scanf("%d%d",&n,&m);vector<vector<int>> dp(n,vector<int>(m,INT_MIN));for(int i=0;i<n;++i){for(int j=0;j<m;++j){scanf("%d",&dp[i][j]);int value=INT_MIN;for(int k=0;k<9;++k){int x=i+dx[k];int y=j+dy[k];if(x>=0 && y>=0){value=max(dp[x][y],value);}}if(value!=INT_MIN) dp[i][j]+=value;}}cout<<dp[n-1][m-1];return 0; }

當然，感謝題解部分提供的遞歸寫法：

#include <bits/stdc++.h> using namespace std; int n,m; int dp(vector<vector<int>>&grid,vector<vector<int>>&memo,int x,int y){ int dx[] = {0,0,0,-1,-1,-1,-2,-2,-3}; int dy[] = {-1,-2,-3,0,-1,-2,0,-1,0}; //base case: if(x<0||y<0)return INT_MIN; if(x==0&&y==0)return grid[0][0]; if(memo[x][y]!=INT_MIN)return memo[x][y]; //condition transfer: int temp = INT_MIN; for(int i=0;i<9;i++){int q = dp(grid,memo,x+dx[i],y+dy[i]);if(q==INT_MIN)continue;temp = max(temp,q); }//備忘錄memo更新 memo[x][y] = temp + grid[x][y]; return memo[x][y]; } int main() {cin>>n>>m; //創建并賦值grid(方格)數組 vector<vector<int>>grid(n,vector<int>(m)); for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>grid[i][j];} } //調用dp函數解決問題：vector<vector<int>> memo(n,vector<int>(m,INT_MIN)); cout<<dp(grid,memo,n-1,m-1); return 0; }

總結

以上是生活随笔為你收集整理的蓝桥杯真题：跳跃的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。