xixi_bang @ 2020-04-12 20:42:10
#include<bits/stdc++.h>
using namespace std;
long long maze[105][105];//表示滑雪点高度
long long dp[105][105];
int main(){
int R,C;
cin>>R>>C;
for(int i=1;i<=R;i++)
for(int j=1;j<=C;j++){
cin>>maze[i][j];
}
for(int i=1;i<=R;i++)
for(int j=1;j<=C;j++){//dp[i][j]表示在(i,j)位置时能够得到的最大滑雪高度
int a=0,b=0,c=0,d=0;
int h=maze[i][j];
if(i+1<=R&&maze[i+1][j]<maze[i][j]) a=1;
if(j+1<=C&&maze[i][j+1]<maze[i][j]) b=1;
if(i-1>=1&&maze[i-1][j]<maze[i][j]) c=1;
if(j-1>=1&&maze[i][j-1]<maze[i][j]) d=1;
//利用a,b,c,d判断max值是否有效
dp[i][j]=max(a*(dp[i+1][j]+h-maze[i+1][j]),max(b*(dp[i][j+1]+h-maze[i][j+1]),
max(c*(dp[i-1][j]+h-maze[i-1][j]),d*(dp[i][j-1]+h-maze[i][j-1]))));
}
long long ans=0;
for(int i=1;i<=R;i++)
for(int j=1;j<=C;j++){
ans=max(dp[i][j],ans);
}
cout<<ans+1<<endl;//高度最后需要+1
}by metaphysis @ 2020-04-12 21:51:25
@xixi_bang
我想您应该是理解错题意了。
输出区域中最长滑坡的长度。我不太清楚照您这样写最后输出的是什么（最大的高度差之和？）。
by xixi_bang @ 2020-04-13 12:31:25
@metaphysis 是的，我理解成最大高度差了，但是如果我把h-maze[i][j]替换成+1为什么也行不通呢
dp[i][j]=max(dp[i][j],max(a*(dp[i+1][j]+1),max(b*(dp[i][j+1]+1),
max(c*(dp[i-1][j]+1),d*(dp[i][j-1]+1)))));by metaphysis @ 2020-04-13 12:41:51
@xixi_bang
这样还不行。举个例子：
2 2
3 4
2 1当你计算高度为3的格子的最大滑雪长度时，由于正下方的格子高度为2，小于3，此时你会得到高度为3的格子的最大滑雪长度为1，然后高度为3的格子就不会再更新了。但是实际上高度为2的格子的最大滑雪长度为2。
也就是说，后续更新的值，您无法知晓，需要使用 DFS 来确定。
by metaphysis @ 2020-04-13 12:43:11
DFS + 备忘。
by xixi_bang @ 2020-04-13 12:59:24
@metaphysis 可以利用优先队列排列之后再进行dp？
by metaphysis @ 2020-04-13 13:04:54
@xixi_bang
您具体描述下思路看看，只要能够保证当今格子的最大滑雪长度是最优值即可，不论你使用何种方法。
by xixi_bang @ 2020-04-13 13:08:15
@metaphysis
#include<bits/stdc++.h>
using namespace std;
long long maze[105][105];//表示滑雪点高度
long long dp[105][105]={1};
struct pix{
int x=0,y=0;
int height=0;
};
struct cmp{
bool operator()(pix& a,pix& b){
if(a.height!=b.height)
return a.height>b.height;
else
return a.x<b.x;
}
};
int main(){
int R,C;
cin>>R>>C;
for(int i=1;i<=R;i++)
for(int j=1;j<=C;j++){
cin>>maze[i][j];
}
priority_queue<pix,vector<pix>,cmp> pri;
for(int i=1;i<=R;i++)
for(int j=1;j<=C;j++)
{
pix t;
t.x=i;
t.y=j;
t.height=maze[i][j];
pri.push(t);
}
long long ans=0;
while(pri.empty()==false){
pix f=pri.top();
pri.pop();
int i=f.x;
int j=f.y;
int a=0,b=0,c=0,d=0;
if(i+1<=R&&maze[i+1][j]<maze[i][j]) a=1;
if(j+1<=C&&maze[i][j+1]<maze[i][j]) b=1;
if(i-1>=1&&maze[i-1][j]<maze[i][j]) c=1;
if(j-1>=1&&maze[i][j-1]<maze[i][j]) d=1;
//利用a,b,c,d判断max值是否有效
dp[i][j]=max(dp[i][j],max(a*(dp[i+1][j]+1),max(b*(dp[i][j+1]+1),
max(c*(dp[i-1][j]+1),d*(dp[i][j-1]+1)))));
ans=max(dp[i][j]+1,ans);
}
cout<<ans<<endl;//高度最后需要+1
}像是这样，有个问题，如何考虑到这种dp需要进行排序后再进行状态转移的问题呢，还有就是dp如何debug呢，我时常是靠自己去想来理解逻辑问题，但是不知道怎么来通过状态变更来找到逻辑的错误
by metaphysis @ 2020-04-13 15:14:40
嗯，我晚上帮您看看，但直觉上觉得可能会行不通，因为排序不是必需的一个步骤。DP就怕大方向想错了，大方向一想错，很难推出递推关系式，递推关系式一错，后面跟着错。
by metaphysis @ 2020-04-13 15:19:10
嗯，似乎是行得通的，因为要求高度严格递减，用优先队列保证了低的高度先处理，你可以自己先构造几组简单的测试数据，看看结果如何。
by metaphysis @ 2020-04-13 19:14:45
@xixi_bang
使用优先队列能够保证最优解，原因前述已经说明，根本原因在于题目约束要求高度要严格递减。对于原网格来说，其递推关系式为：
dp[i][j] = max{dp[x][y] + 1}，|i－x|＋|j－y|＝1，h[x][y]＜h[i][j]使用优先队列保证了递推关系式的正确性。应该说，使用优先队列是根据递推关系式得到的一种实现，而不是说先使用优先队列排序后，在来推导递推关系式。