蒟蒻求助,第二点莫名TLE

P1434 [SHOI2002] 滑雪

skiy_gyx @ 2019-01-27 20:49:00

vector版本的宽搜应该没啥问题啊,怎会超时??

#include<bits/stdc++.h>
using namespace std;
int ans=1,n,m,a[110][110];
vector<int>x;
vector<int>y;
int f[110][110];
const int dir[5][5]={
    {0,1},{1,0},{0,-1},{-1,0}
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            x.clear();
            y.clear();
            memset(f,0,sizeof(f));
            int head=0,tail=0;
            x.push_back(i);
            y.push_back(j);
            f[i][j]=1;
            while(head<=tail){
                for(int i=0;i<4;i++){
                    int tx=x[head]+dir[i][0];
                    int ty=y[head]+dir[i][1];
                    if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&
                    f[x[head]][y[head]]+1>f[tx][ty]
                    &&a[x[head]][y[head]]>a[tx][ty]){
                        tail++;
                        f[tx][ty]=f[x[head]][y[head]]+1;
                        ans=max(ans,f[tx][ty]);
                        x.push_back(tx);
                        y.push_back(ty);  
                    }
                } 
                head++;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

by kkksx @ 2019-01-27 21:04:53

常数大了吧,而且好像也没有记忆化啊


by skiy_gyx @ 2019-01-27 21:08:20

@皮皮鳝 宽搜呀,记忆化写残了


by kkksx @ 2019-01-27 21:11:50

然而此题记搜第二个点只要6ms


by kkksx @ 2019-01-27 21:21:11

@gyxAC之神 面对构造数据可能入队很多次吧,反正感觉代码看起来没什么问题,我太蒟了


by 樱花飞舞 @ 2019-02-05 21:54:25

数组开到301


|