//来自算法基础课
记忆化搜索
dfs+记忆化 = DP
DP的本质不就是爆搜的优化嘛
(也有国集大佬说本质是状态压缩的)
1.状态表示:
集合:所有从(i,j)这个点开始滑的路径长度
属性:max
2.状态计算:
就是搜索,每个点能不能向上下左右动
下面代码中的f[x][y] = max(f[x][y],dp(xx,yy)+1);
实际上就是向四个方向判断之后转移:
if(a[i-1][j]<now) f[i][j] = max(f[i][j],f[i-1][j]+1);//上
if(a[i+1][j]<now) f[i][j] = max(f[i][j],f[i+1][j]+1);//下
if(a[i][j-1]<now) f[i][j] = max(f[i][j],f[i][j-1]+1);//左
if(a[i][j+1]<now) f[i][j] = max(f[i][j],f[i][j+1]+1);//右
(bu)意外的收获:
DP没有后效性 <==> 抽象出来的图论模型是一个拓扑图
(众所周知DP其实就是一个DAG嘛)
CODE
#include<bits/stdc++.h>
#define read(x) scanf("%d",&x)
using namespace std;
const int N = 310;
int n,m,a[N][N],f[N][N];
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int dp(int x,int y) {
if(f[x][y]!=0) return f[x][y]; //记忆化的好处
f[x][y] = 1;//初始化
for(register int i=0; i<4; i++) {
int xx = x+dx[i];
int yy = y+dy[i];
if(xx>=1&&xx<=n && yy>=1&&y<=m && a[x][y]>a[xx][yy])
f[x][y] = max(f[x][y],dp(xx,yy)+1);
}
return f[x][y];
}
int main() {
read(n),read(m);
for(register int i=1; i<=n; i++)
for(register int j=1; j<=m; j++)
read(a[i][j]);
int ans = 0;
for(register int i=1; i<=n; i++)
for(register int j=1; j<=m; j++)
ans = max(ans,dp(i,j));
printf("%d\n",ans);
return 0;
}
这里再提供一种做法
priority_queue+bfs式的dp
这个dp的思路很清晰
跑的也很快
时间复杂度好像是O(n)?
我不会算时间复杂度诶
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
struct node{
int i,j,num;
};
struct cmp1{
bool operator()(node x,node y){
return x.num>y.num;
}
};
priority_queue<node,vector<node>,cmp1>q;
int n,m,f[101][101],g[101][101],maxn;
void bfs() {
while(!q.empty()){
node tmp = q.top();
int i = tmp.i;
int j = tmp.j;
int now = tmp.num;
q.pop();
if(g[i-1][j]<now) f[i][j]=max(f[i][j],f[i-1][j]+1);
if(g[i+1][j]<now) f[i][j]=max(f[i][j],f[i+1][j]+1);
if(g[i][j-1]<now) f[i][j]=max(f[i][j],f[i][j-1]+1);
if(g[i][j+1]<now) f[i][j]=max(f[i][j],f[i][j+1]+1);
if(maxn<f[i][j]) maxn=f[i][j];
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
f[i][j]=1;
scanf("%d",&g[i][j]);
node a;
a.i=i;
a.j=j;
a.num=g[i][j];
q.push(a);
}
bfs();
printf("%d\n",maxn);
return 0;
}
第二份代码不能ac
他数组开小了,改成310就可以了
orz跑的好快orz,我自己yy出一个nmlogn的恶心复杂度跑了400多ms
if(f[x][y]!=0) return f[x][y]; 这一步可不可以理解为因为已经搜过了,所以沿着搜过的路继续走下去就可以了?