[题解] luogu P1434 [SHOI2002]滑雪

既然全机房都在写这道题,那我就毫不犹豫地抢个沙发发布题解吧

其实是很简单的,只要从最低往最高去找四周最大的步数就行了。因为高处要往低处走,所以只要先DP一下小的数再按顺序找就行了。

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
template<typename T>inline void scan(T &x)
{
    char ch;
    bool f=0;
    ch=getchar();
    x=0;
    while(!isdigit(ch)&&ch!='-') ch=getchar();
    if(ch=='-') f=1,ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(f==1) x=-x;
}
struct sss
{
    int zuo;
    int you;
    int zhi;
}a[10005];
int m,n,tot,maxn;
int s[105][105];
int ans[105][105];
int zuo[5]={0,0,0,-1,1};
int you[5]={0,1,-1,0,0};
bool cmp(const sss &x,const sss &y)//你懂得,sort的必须
{
    return x.zhi<y.zhi;
}
int main()
{
    scan(n);
    scan(m);
    for(register int i=1;i<=n;i++)
        for(register int j=1;j<=m;j++)
        {
            scan(a[++tot].zhi);
            a[tot].zuo=i;
            a[tot].you=j;
            s[i][j]=a[tot].zhi;
        }
    sort(a+1,a+tot+1,cmp);//排出序来
    for(register int i=1;i<=tot;i++)
    {
        for(register int j=1;j<=4;j++)
            if(a[i].zuo+zuo[j]<=n&&a[i].zuo+zuo[j]>0&&a[i].you+you[j]>0&&a[i].you+you[j]<=m&&s[a[i].zuo+zuo[j]][a[i].you+you[j]]<a[i].zhi)
                ans[a[i].zuo][a[i].you]=max(ans[a[i].zuo+zuo[j]][a[i].you+you[j]]+1,ans[a[i].zuo][a[i].you]);//DP方程
        maxn=max(maxn,ans[a[i].zuo][a[i].you]);
    }
    printf("%d\n",maxn+1);//最后的那个数没有记录步数,所以要加1
    return 0;
}
Last modification:March 2nd, 2019 at 08:28 pm

One comment

  1. L我的鱼不吃

    太强了

Leave a Comment