题意

其实就是一条二维的LIS，但是还是做的一愣一愣的，多努力。
考虑$dp[i][j]$为从(i,j)出发的二维LIS的最大值，那么$dp[i][j]=max\{dp[i−di[k]][j−dj[k]]\}+1$，取dp值时要求严格递减。否则值为1。

分析

#include <bits/stdc++.h>

#define MP make_pair

#define PB push_back

#define fi first

#define se second

#define ZERO(x) memset((x), 0, sizeof(x))

#define ALL(x) (x).begin(),(x).end()

#define rep(i, a, b) for (int i = (a); i <= (b); ++i)

#define per(i, a, b) for (int i = (a); i >= (b); --i)

#define QUICKIO                  \

    ios::sync_with_stdio(false); \

    cin.tie(0);                  \

    cout.tie(0);

using namespace std;

using ll = long long;

using ull = unsigned long long;

using pi = pair<int, int>;

using pii = pair<int, pi>;

template<typename T>

T

read()

{

    T tmp; cin>>tmp;

    return tmp;

}

int arr[105][105],dp[105][105],n,m;

const int dx[]={0,1,0,-1},

          dy[]={1,0,-1,0};

int

solve(int x,int y)

{

    //cout<<x<<" "<<y<<endl;

    if(dp[x][y]!=-1) return dp[x][y];

    else

    {

        int tmpans=1;

        rep(i,0,3)

        {

            int tx=x+dx[i],

                ty=y+dy[i];

            if(tx>=1 && tx<=n && ty>=1 && ty<=m

            && arr[tx][ty]<arr[x][y])

            {

                tmpans=max(tmpans,solve(tx,ty)+1);

            }

        }

        return dp[x][y]=tmpans;

    }

}

int

main()

{

    int T; cin>>T;

    while(T--)

    {

        string p; cin>>p>>n>>m;

        rep(i, 1, n)

            rep(j, 1, m)

                { cin>>arr[i][j]; }

        memset(dp,-1,sizeof(dp));

        int ans=-1;

        rep(i, 1, n)

            rep(j, 1, m)

            {

                if(dp[i][j]==-1)

                    dp[i][j]=solve(i,j);

                ans=max(ans,dp[i][j]);

            }

        cout<<p<<": "<<ans<<endl;

    }

    return 0;

}

巴特西

「日常训练」 Longest Run on a Snowboard （UVA-10285）

题意

分析

最新文章

热门文章