20分，打了两个循环，每次枚举2次方向，不知道解题思路是否正确

P1434 [SHOI2002] 滑雪

Main_WF @ 2022-07-10 11:22:44

f[i][j]表示从(i,j)开始滑雪的最大长度我想了转移方程是f[i][j]=max(f[i][j-1]+滑雪长度,f[i-1][j]+滑雪长度,f[i][j+1]+滑雪长度,f[i+1][j]+滑雪长度)，考虑到f[i][j]由四个方向转移而来，而对于i,j的枚举分别是从1-n,1-m的，所以在转移f[i][j]时,f[i+1][j]和f[i][j+1]为空，所以我就打了两个循环。结果出来后，A 20 W 80

#include<bits/stdc++.h>
using namespace std;
int f[105][105],h[105][105],n,m,dx[4]={0,-1,0,1},dy[4]={-1,0,1,0},ans=-1;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>f[i][j];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            for(int k=0;k<=1;k++)
            {
                int tx=i+dx[k];int ty=j+dy[k];
                if(h[tx][ty]>=h[i][j]|tx<1|tx>n|ty<1|ty>m)continue;
                f[i][j]=max(f[i][j],f[tx][ty]+h[i][j]-h[tx][ty]);
            }
        }   
    }
    for(int i=n;i>=1;i--)
    {
        for(int j=m;j>=1;j--)
        {
            for(int k=2;k<=3;k++)
            {
                int tx=i+dx[k];int ty=j+dy[k];
                if(h[tx][ty]>=h[i][j]|tx<1|tx>n|ty<1|ty>m)continue;
                f[i][j]=max(f[i][j],f[tx][ty]+h[i][j]-h[tx][ty]);
            }
        }   
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            ans=max(ans,f[i][j]);
    cout<<ans;
}

by Main_WF @ 2022-07-10 11:27:57

看了题解，发现滑坡长度每次+1，修改代码后测评结果不变

#include<bits/stdc++.h>
using namespace std;
int f[105][105],h[105][105],n,m,dx[4]={0,-1,0,1},dy[4]={-1,0,1,0},ans=0;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>f[i][j];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            for(int k=0;k<=1;k++)
            {
                int tx=i+dx[k];int ty=j+dy[k];
                if(h[tx][ty]>=h[i][j]|tx<1|tx>n|ty<1|ty>m)continue;
                f[i][j]=max(f[i][j],f[tx][ty]+1);
            }
        }   
    }
    for(int i=n;i>=1;i--)
    {
        for(int j=m;j>=1;j--)
        {
            for(int k=2;k<=3;k++)
            {
                int tx=i+dx[k];int ty=j+dy[k];
                if(h[tx][ty]>=h[i][j]|tx<1|tx>n|ty<1|ty>m)continue;
                f[i][j]=max(f[i][j],f[tx][ty]+1);
            }
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            ans=max(ans,f[i][j]);
    cout<<ans;
}

by Main_WF @ 2022-07-10 11:42:57

突然发现盲点！我输入的居然是f[][]

by Main_WF @ 2022-07-10 11:53:23

修改之后样例都过不了了...

#include<bits/stdc++.h>
using namespace std;
int f[105][105],h[105][105],n,m,dx[4]={0,-1,0,1},dy[4]={-1,0,1,0},ans=1;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>h[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            f[i][j]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            for(int k=0;k<=1;k++)
            {
                int tx=i+dx[k];int ty=j+dy[k];
                if(h[tx][ty]>=h[i][j]|tx<1|tx>n|ty<1|ty>m)continue;
                f[i][j]=max(f[i][j],f[tx][ty]+1);
            }
        }   
    }
    for(int i=n;i>=1;i--)
    {
        for(int j=m;j>=1;j--)
        {
            for(int k=2;k<=3;k++)
            {
                int tx=i+dx[k];int ty=j+dy[k];
                if(h[tx][ty]>=h[i][j]|tx<1|tx>n|ty<1|ty>m)continue;
                f[i][j]=max(f[i][j],f[tx][ty]+1);
            }
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            ans=max(ans,f[i][j]);
    cout<<ans;
}