记忆化求找错T一点

P1434 [SHOI2002] 滑雪

ZXZ695 @ 2018-06-29 12:54:57

如标题 第二点T了

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int r,c,ans=0,a[205][205],b[10509][4],asd[205][205],qwe[205][205];//行R           //列C
int zx[5]={0,1,0,-1,0},zc[5]={0,0,1,0,-1};
void sq(int l,int r)
{
    int i,j,mid;
    i=l;
    j=r;
    mid=b[(i+j)/2][2];
    do
    {
        while(b[i][2]<mid)i++;
        while(b[j][2]>mid)j--;

    if(i<=j)
    {
    swap(b[i][2],b[j][2]);
    swap(b[i][1],b[j][1]);
    swap(b[i][0],b[j][0]);
    i++;j--;
    }

    }
    while(i<=j);
    if(i<r) sq(i,r);
    if(l<j) sq(l,j);
}
void dfs(int x,int y,int ti)
{
    ans=max(ti,ans);
    if(qwe[x][y]>ti)return;
    else
    qwe[x][y]=max(qwe[x][y],ti);
    for(int i=1;i<=4;i++)
    {
        int xx=x+zx[i],yy=y+zc[i];
        if(xx<1||xx>r||yy<1||yy>c)continue;
        if(a[xx][yy]>=a[x][y])continue;
        ti++;
        dfs(xx,yy,ti);
        ti--;
    }
}
int main()
{
cin>>r>>c;
int top=0;
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
{
    cin>>a[i][j];
    top++;
    b[top][0]=i;
    b[top][1]=j;
    b[top][2]=a[i][j];
}
sq(1,top);
for(int i=1;i<=top;i++)
{
asd[b[i][0]][b[i][1]]=i;
}
for(int i=top;i>=1;i--)
{ 
if(asd[b[i][0]][b[i][1]]<=ans)continue;
if(qwe[b[i][0]][b[i][1]]&& qwe[b[i][0]][b[i][1]] <= ans)continue;
dfs(b[i][0],b[i][1],1);  
}
cout<<ans;
return 0;
}

by 黄逸昕 @ 2018-06-29 13:15:19

把数据下载下来试一下

就是你除AC/CE外都可下载第一个出错的数据点


by Cyan_rose @ 2018-07-17 11:59:51

你可以试试多提交几次~我第一遍90第二遍莫名其妙就A了


|