judgejudge @ 2019-02-25 18:38:03
#include <iostream>
#include <cstdio>
using namespace std;
int a[10001][10001];
int f[10001][10001];
int n,m;
void read(int &a){
a=0;int d=1;char c;
while(c=getchar(),c<'0'||c>'9')if(c=='-')d=-1;a=a*10+c-48;
while(c=getchar(),c>='0'&&c<='9')a=a*10+c-48;
a*=d;
}
void write(int x){
if(x<0){
x=-x;
putchar(45);
}
if(x) write(x/10);
else return;
putchar(x%10+48);
}
inline int dp(int s1,int s2){
int i,j;
if(s1>=1&&s1<=n&&s2>=1&&s2<=m){
if(a[s1-1][s2]>a[s1][s2]){
f[s1-1][s2]=max(f[s1-1][s2],f[s1][s2]+1);
dp(s1-1,s2);
}
if(a[s1+1][s2]>a[s1][s2]){
f[s1+1][s2]=max(f[s1+1][s2],f[s1][s2]+1);
dp(s1+1,s2);
}
if(a[s1][s2-1]>a[s1][s2]){
f[s1][s2-1]=max(f[s1][s2-1],f[s1][s2]+1);
dp(s1,s2-1);
}
if(a[s1][s2+1]>a[s1][s2]){
f[s1][s2+1]=max(f[s1][s2+1],f[s1][s2]+1);
dp(s1,s2+1);
}
}
}
int main(){
int i,j,k;
int row,col;
int minl=1000000;
read(n);
read(m);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
read(a[i][j]);
if(a[i][j]<minl){
minl=a[i][j];
row=i;
col=j;
}
}
int maxl=0;
f[row][col]=1;
dp(row,col);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(maxl<f[i][j])maxl=f[i][j];
write(maxl);
return 0;
}
by judgejudge @ 2019-02-26 20:38:15
@万万没想到 我又把那一句改成这样了:
if(s1>=1&&s1<=n&&s2>=1&&s2<=m&&f[s1][s2]>0){
但是还是70分。。。
by judgejudge @ 2019-02-26 20:39:12
@万万没想到 发现自己改错了,对不起
by judgejudge @ 2019-02-26 20:49:07
@万万没想到 我觉得我貌似不能判断坐标是否有值,因为我这程序它要不断更新
by judgejudge @ 2019-02-26 20:50:39
@万万没想到 而且我还是觉得我这个深度优先搜索不像动规那样好记忆化
by 万万没想到 @ 2019-02-27 18:22:05
@judgejudge
记忆化应该在开头打,值先比较最后赋值
循环找最大值应该循环递归,因为最后赋值,保证每个节点的最优子结构
递归函数如下
inline int dp(int s1,int s2){
if(f[s1][s2])return f[s1][s2];
int i,j,Max=0;
if(s1>=1&&s1<=n&&s2>=1&&s2<=m){
if(a[s1-1][s2]>a[s1][s2]){
Max=max(Max,dp(s1-1,s2)+1);
}
if(a[s1+1][s2]>a[s1][s2]){
Max=max(Max,dp(s1+1,s2)+1);
}
if(a[s1][s2-1]>a[s1][s2]){
Max=max(Max,dp(s1,s2-1)+1);
}
if(a[s1][s2+1]>a[s1][s2]){
Max=max(Max,dp(s1,s2+1)+1);
}
}
f[s1][s2]=Max;
return f[s1][s2];
}
循环比较如下
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
if(maxl<dp(i,j))maxl=f[i][j];
}
}
最后输出maxl+1
by judgejudge @ 2019-02-27 18:32:44
@万万没想到 哇!!!!太谢谢了!!!现在过了!!!
by 万万没想到 @ 2019-02-27 18:36:05
@judgejudge
不用谢共同进步
by judgejudge @ 2019-02-27 18:44:57
@万万没想到 好的,再次感谢!!