巨佬神犇请点击!!!70分代码求助!!!

P1434 [SHOI2002] 滑雪

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

@万万没想到 好的,再次感谢!!


上一页 |