$$\LARGE{\color{Orange}{\mathbf{Note-各种题目收录} } }$$
记忆化搜索 $dp$ 可以帮你解决,$dp$ 的递推顺序
就比如这道题,直接采取循环来做有点复杂,(。^▽^)
但是我相信一定有佬说你可以使用堆,每次从当前值最大的位置递推,就可以得到答案
确实是一个好办法(doge
code
#include <bits/stdc++.h>
#define fastio() ios::sync_with_stdio(0),\
cin.tie(0),cout.tie(0);
#define lowbit(x) (x & -x)
#define endl '\n'
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef tuple<int,int,int> TRI;
typedef unsigned long long ULL;
constexpr int N = 110;
int n,K;
int dp[N][N],w[N][N];
int dfs(int u,int v)
{
if(~dp[u][v]) return dp[u][v];
int res = 0;
for(int k = 1;k <= K;k ++ )
{
if(u - k >= 0 && w[u - k][v] > w[u][v])
res = max(res,dfs(u - k,v));
if(v - k >= 0 && w[u][v - k] > w[u][v])
res = max(res,dfs(u,v - k));
if(u + k < n && w[u + k][v] > w[u][v])
res = max(res,dfs(u + k,v));
if(v + k < n && w[u][v + k] > w[u][v])
res = max(res,dfs(u,v + k));
}
return dp[u][v] = res + w[u][v];
}
int main()
{
fastio();
while(cin >> n >> K,~n && ~K)
{
memset(dp,-1,sizeof dp);
for(int i = 0;i < n;i ++ )
for(int j = 0;j < n;j ++ )
cin >> w[i][j];
cout << dfs(0,0) << endl;
}
return 0;
}
Orz,写的太好了