HDU 1087 FatMouse and Cheese——DP

HDU 1087 FatMouse and Cheese——DP

最长滑雪路径的一个小变形，注意从（0,0）开始

#include #include #include #include using namespace std;const int maxn = 1010;int N, K, a[maxn][maxn], dp[maxn][maxn];int dfs(int x, int y) { if (dp[x][y] != -1) return dp[x][y]; int W = (x - K >= 1) ? x - K : 1; int S = (x + K <= N) ? x + K : N; int A = (y - K >= 1) ? y - K : 1; int D = (y + K <= N) ? y + K : N; int maxv = 0; for (int i = W; i <= S; i++) if (a[x][y] < a[i][y]) maxv = max(maxv, dfs(i, y)); for (int i = A; i <= D; i++) if (a[x][y] < a[x][i]) maxv = max(maxv, dfs(x, i)); return dp[x][y] = maxv + a[x][y];}int main() { while (~scanf("%d %d", &N, &K)) { if (N == -1 || K == -1) break; memset(dp, -1, sizeof(dp)); for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { scanf("%d", &a[i][j]); } } printf("%d\n", dfs(1, 1)); }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。