舅舅孩子 #4AC 剩下都MLE 求大佬优化

P1434 [SHOI2002] 滑雪

白熊不爱A @ 2019-10-05 22:17:32

代码如下:

#include<iostream>
#include<algorithm>
using namespace std;
int R,C;//r行c列
int map[101][101],proj[101][101];//rst为周围情况,1上,2下,3左,4右
struct p{
    int val,ff,gg;//最长滑道 x y
}rst[6];
void sct(){
    proj[1][1]=1;
    return;
}
bool cmp(p a,p b){
    return a.val>b.val;
}
int prog(int i,int j){
    if(proj[i][j]) return proj[i][j];//记忆化
    //搜集周围情况
    if(i==1) rst[1].val=0; else rst[1].val=prog(i-1,j);//点在第一行
    if(i==R) rst[2].val=0; else rst[2].val=prog(i+1,j);//点在第R行
    if(j==1) rst[3].val=0; else rst[3].val=prog(i,j-1);//点在第一列
    if(i==C) rst[4].val=0; else rst[4].val=prog(i,j+1);//点在第c列
    sort(rst+1,rst+4+1,cmp);//排序
    int s=1;
    //在周围点中找最大的滑道 而且要能划过去
    while(s<=4){
        if(map[rst[s].ff][rst[s].gg]<=map[i][j]&&rst[s].val!=0){
            proj[i][j]=rst[s].val+1;//自己最长滑道=该点最长滑道+1
            break;//跳出以防多加
        }
        s--;
    }
    return proj[i][j];
}
int main(){
    sct();
    int max=0;
    cin>>R>>C;
    for(int i=1;i<=R;++i){
        for(int j=1;j<=C;++j){
            cin>>map[i][j];
            prog(i,j);
        }
    }
    //遍历所有点 找最大值
    for(int i=1;i<=R;++i){
        for(int j=1;j<=C;++j){
            if(proj[i][j]>max){
                max=proj[i][j];
            }
        }
    }
    cout<<max;
    return 0;
}

by zr太弱了 @ 2019-10-05 22:40:16

@白熊不爱A

状态转移方程:f[i][j]=max{f[i±1][j]+1,f[i][j±1}+1,f[i][j]}


|