UESTC1271Searchgold

题目链接&＃xff1a;http://acm.uestc.edu.cn/#/problem/show/1271
题意&＃xff1a;一个N*M的矩阵&＃xff0c;每个格子有一个数&＃xff0c;然后每个人在某一个格子有4种走法&＃xff0c;然后问从&＃xff08;1&＃xff0c;1&＃xff09;出发能得到的最大价值。
解法&＃xff1a;
矩阵DP
算法复杂度&＃xff1a;0(N*M)
memset(dp,-1,sizeof(dp));dp[1][1]&＃61;a[1][1];
dp[i][j]&＃61;max(dp[i-1][j],dp[i][j-1],dp[i-1][j-2],dp[i-2][j-1])>&＃61;0?max(dp[i-1][j],dp[i][j-1],dp[i-1][j-2],dp[i-2][j-1])&＃43;a[i][j]:-1

#include
using namespace std;
const int maxn &＃61; 1010;
int n,m,a[maxn][maxn], dp[maxn][maxn];
bool check(int x, int y){if(x>&＃61;1&&x<&＃61;n&&y>&＃61;1&&y<&＃61;m) return 1;return 0;
}
int main()
{scanf("%d%d",&n,&m);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)for(int j&＃61;1;j<&＃61;m;j&＃43;&＃43;)scanf("%d",&a[i][j]);memset(dp,-1,sizeof(dp));dp[1][1]&＃61;a[1][1];for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;){for(int j&＃61;1; j<&＃61;m; j&＃43;&＃43;){if(i&＃61;&＃61;1&&j&＃61;&＃61;1) continue;int mx &＃61; -100000000;if(check(i-1,j)) mx&＃61;max(mx,dp[i-1][j]);if(check(i,j-1)) mx&＃61;max(mx,dp[i][j-1]);if(check(i-1,j-2)) mx&＃61;max(mx,dp[i-1][j-2]);if(check(i-2,j-1)) mx&＃61;max(mx,dp[i-2][j-1]);if(mx>&＃61;0){dp[i][j]&＃61;mx&＃43;a[i][j];}else{dp[i][j]&＃61;-1;}}}int ans&＃61;-1000000;for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;)for(int j&＃61;1; j<&＃61;m; j&＃43;&＃43;)ans&＃61;max(ans,dp[i][j]);printf("%d\n", ans);return 0;
}