记忆化搜索DP

题目描述

滑格子

样例

算法1

(暴力枚举) $O(n^2)$

#include<bits/stdc++.h>

using namespace std;

const int N = 310 ;

int g[N][N] ;

int f[N][N][N];
int n , m ;

int get(int i ,int j )
{
    return (i - 1) * m + j - 1;
}

void bfs(int c ,int i ,int j)
{
    int dx[] = { 0 , -1 , 0 , 1 };
    int dy[] = { 1 ,  0 , -1 , 0 };
    bool st[N][N];
    memset(st , false , sizeof st);
    queue<pair<int,int>> hh;

    hh.push({ i , j });
    f[i][j][c] = 1;
    st[i][j] = true ;
    while(hh.size())
    {
        auto t = hh.front();
        hh.pop();
        i = t.first , j = t.second ;
        st[i][j] = true ;
        for(int k = 0 ; k <= 3 ; k ++)
        {
            int a = i + dx[k] ;
            int b = j + dy[k] ;
            if( a >= 1 && a <= n && b >= 1 && b <= m  && g[a][b] < g[i][j] && !st[a][b] )
            {
               f[a][b][c] = max( f[i][j][c] + 1 , f[a][b][c] );
               hh.push({ a , b });
            }
        }
    }
}

int main()
{
    cin >> n >> m ;
    for(int i = 1 ; i <= n ; i ++ )
       for(int j = 1 ; j <= m ; j ++ )
          cin >> g[i][j];

    for(int i = 1 ; i <= n ; i ++ )
       for(int j = 1 ; j <= m ; j ++ )
          {
              int c = get(i , j);
              bfs(c , i , j);
          }
    int res = 0 ;
    for(int i = 0 ; i <= n * m - 1 ; i ++ )
       for(int k = 1 ; k <= n ; k ++)
          for(int j = 1 ; j <= m ; j ++)
             res = max(res , f[k][j][i]);

    cout << res << endl;
}

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla