ddxw @ 2022-05-07 02:37:41
wa了#1和最后三个,看了一个多小时改了好几次还是不行,快看吐了,有无大佬能找一下错误,用的dp
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
static int r, c, hd[10000], ord[10000],dp[10000];
inline int m(int a, int b)
{
return a > b ? a : b;
}
bool Sort(int a, int b)
{
return hd[a] < hd[b];
}
int main()
{
int int M = 0;
cin >> r >> c;
for (int i = 0; i < r * c; i++)
{
cin >> hd[i];
ord[i] = i;
}
sort(ord, ord + r * c, Sort);
int max = 0;
for (int i = 0; i < r * c; i++)
{
if (i == 0) { dp[ord[i]] = 1; M = 1; continue; }
int up = 0, down = 0, left = 0, right = 0;
if (ord[i] - c >= 0)
if (hd[ord[i] - c] < hd[ord[i]]) up = hd[ord[i]] - hd[ord[i] - c] + dp[ord[i] - c];
if (ord[i] + c < r * c)
if (hd[ord[i] + c] < hd[ord[i]]) down = hd[ord[i]] - hd[ord[i] + c] + dp[ord[i] + c];
if (ord[i] % c != 0)
if (hd[ord[i]] > hd[ord[i] - 1]) left = hd[ord[i]] - hd[ord[i] - 1] + dp[ord[i] - 1];
if ((ord[i] + 1) % c != 0)
if (hd[ord[i]] > hd[ord[i] + 1]) right = hd[ord[i]] - hd[ord[i] + 1] + dp[ord[i] + 1];
if (up == 0 && down == 0 && left == 0 && right == 0) dp[ord[i] == 0];
else dp[ord[i]] = m(up, m(down, m(left, right)));
M = M > dp[ord[i]] ? M : dp[ord[i]];
}
cout<<M;
}
by wcyQwQ @ 2022-05-07 06:37:20
讲道理,有点看不懂
话说这题不是记忆化搜索吗