交替调用DFS
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 509;
int a[N];
int f1[N],f2[N];
int n;
int dfs1(int u);
int dfs2(int u);
int main()
{
cin >> n;
for(int i=1; i<=n; i++) cin >> a[i];
int ans = 0;
for(int i=1; i<=n; i++)
{
ans = max(dfs1(i),max(dfs2(i),ans));
}
cout<<ans<<"\n";
return 0;
}
int dfs1(int u)
{
if(f1[u]) return f1[u];
f1[u] = 1;
for(int i=u+1; i<=n; i++)
{
if(a[i] > a[u])
{
f1[u] = max(f1[u],dfs2(i) + 1);
}
}
return f1[u];
}
int dfs2(int u)
{
if(f2[u]) return f2[u];
f2[u] = 1;
for(int i=u+1; i<=n; i++)
{
if(a[i] < a[u])
{
f2[u] = max(f2[u],dfs1(i) + 1);
}
}
return f2[u];
}
DFS对于Size与MAX，MIN:
#include<iostream>
#include<cstring>
using namespace std;
const int N = 2e5+9;
int e[N],ne[N],w[N],h[N],idx;
bool st[N];
int root,n,k;
int Size[N],MAX[N],MIN[N];
void add(int a,int b)
{
e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
int dfs(int u)
{
st[u] = true;
Size[u] = 1;
MAX[u] = w[u],MIN[u] = w[u];
for(int i=h[u]; i!=-1; i=ne[i])
{
int j = e[i];
if(!st[j])
{ // [j] [u]; ??????
//deep[u] = deep[j] + 1; 先统计再次递归！
//自上而下还是自下而上！
dfs(j);
Size[u] += Size[j];
MAX[u] = max(MAX[u],MAX[j]);
MIN[u] = min(MIN[u],MIN[j]);
}
}
return Size[u];
}
int main()
{
int _;
scanf("%d",&_);
while(_--)
{
idx = 0;
memset(st,false,sizeof(st));
memset(h,-1,sizeof(h));
memset(Size,0,sizeof(Size));
memset(MAX,0,sizeof(MAX));
memset(MIN,0x3f,sizeof(MIN));
scanf("%d%d",&n,&k);
for(int i=1; i<=n; i++) scanf("%d",&w[i]);
for(int i=1; i<n; i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b),add(b,a);
}
scanf("%d",&root);
dfs(root);
int x = -1,ans = 0;
for(int i=1; i<=n; i++)
{
if(Size[i] <= k && MAX[i] - MIN[i] > x)
{
x = MAX[i] - MIN[i];
ans = i;
}
}
printf("%d\n",ans);
}
return 0;
}
状压枚举+BFS
E - 小红的rpg游戏 对标cf 1600 分！
https://ac.nowcoder.com/acm/contest/11218/E
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
const int N = 109;
const int dx[] = {1,-1,0,0};
const int dy[] = {0,0,1,-1};
char s[N][N];
int vis[N][N];
int n,m,h;
pair<int,int> g[N];
struct node
{
int x,y,step;
};
struct mon
{
int x,y,blood;
};
vector<mon> ve;
bool have(int x,int y)
{
for(int i=0; i<ve.size(); i++)
{
if(g[i].first == x && g[i].second == y) return true;
}
return false;
}
int bfs()
{
memset(vis,0,sizeof vis);
queue<node> qu;
qu.push({1,1,0});
vis[1][1] = 1;
while(!qu.empty())
{
auto t = qu.front();
qu.pop();
if(t.x == n && t.y == m)
{
return t.step;
}
for(int i=0; i<4; i++)
{
int xx = t.x + dx[i];
int yy = t.y + dy[i];
if(xx <= n && xx >= 1 && yy <= m && yy >= 1)
{
if(!vis[xx][yy] && (s[xx][yy] == '.'|| have(xx,yy)))
{
vis[xx][yy] = 1;
qu.push({xx,yy,t.step+1});
}
}
}
}
return -1;
}
int main()
{
cin >> n >> m >> h;
for(int i=1; i<=n; i++)
{
cin >> s[i] + 1;
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++) if(isdigit(s[i][j])) ve.push_back({i,j,s[i][j] - '0'});
}
int ans = 1e9+7;
for(int i=0; i< 1<<ve.size(); i++)
{
memset(g,0,sizeof(g));
int sum = 0;
for(int j=0; j< ve.size(); j++)
{
if(1 << j & i)
{
g[j].first = ve[j].x,g[j].second = ve[j].y;
sum += ve[j].blood;
}
}
if(sum >= h) continue;
int t = bfs();
if(t != -1) ans = min(ans,t);
}
if(ans == 1e9+7) printf("-1\n");
else printf("%d\n",ans);
return 0;
}
洛谷：P2802 回家
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int N = 209;
int n,m;
int mp[N][N],vis[N][N];
int ans;
const int dx[] = {1,-1,0,0};
const int dy[] = {0,0,1,-1};
struct node
{
int x,y,step,blood;
};
queue<node> qu;
void bfs()
{
while(!qu.empty())
{
auto t = qu.front();
if(mp[t.x][t.y] == 3 && t.blood > 0)
{
ans = t.step;
break;
}
vis[t.x][t.y] = max(vis[t.x][t.y],t.blood);
qu.pop();
for(int i=0; i<4; i++)
{
int xx = t.x + dx[i];
int yy = t.y + dy[i];
if(mp[xx][yy] != 0)
{
if(vis[t.x][t.y] > vis[xx][yy] && t.blood > 1)
{
if(mp[xx][yy] == 4) qu.push({xx,yy,t.step+1,6});
else qu.push({xx,yy,t.step+1,t.blood - 1});
}
}
}
}
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for(int i=1; i<=n ; i++)
{
for(int j=1; j<=m; j++)
{
cin >> mp[i][j];
if(mp[i][j] == 2) qu.push({i,j,0,6}),vis[i][j] = 6;
}
}
ans = -1;
bfs();
cout<<ans<<"\n";
return 0;
}
数据已经加强过了，DFS过不去的！
//可行性剪枝与最优性剪枝！
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int N = 109;
const int dx[] = {1,-1,0,0};
const int dy[] = {0,0,1,-1};
char s[N][N];
int vis[N][N];
int n,m,h;
int ans,f;
void dfs(int x,int y,int h,int step)
{
if(step > ans && f == 1) return;
if(x == n && y == m)
{
ans = min(ans,step);
f = 1;
return;
}
vis[x][y] = 1;
for(int i=0; i<4; i++)
{
int xx = x + dx[i];
int yy = y + dy[i];
if(xx >= 1 && xx <= n && yy >= 1 && yy <= m)
{
if(!vis[xx][yy] && s[xx][yy] != '*')
{
if(s[xx][yy] == '.')
{
dfs(xx,yy,h,step+1);
}
else if(isdigit(s[xx][yy]))
{
int t = s[xx][yy] - '0';
if(h - t > 0)
{
dfs(xx,yy,h - (s[xx][yy] - '0'),step+1);
}
}
}
}
}
vis[x][y] = 0;
}
int main()
{
scanf("%d%d%d",&n,&m,&h);
for(int i=1; i<=n; i++) scanf("%s",s[i] + 1);
ans = 1e9;
f = 0;
dfs(1,1,h,0);
if(f) printf("%d\n",ans);
else printf("-1\n");
return 0;
}
搜索与剪枝
//记忆化搜索Fi
#include<iostream>
#include<string.h>
using namespace std;
const int N = 1e3+9;
typedef long long ll;
ll Fi[N],dp[N];
long long fi(int n)
{
if(n == 1 || n == 2) return 1;
if(Fi[n]) return Fi[n];
Fi[n] = fi(n-1) + fi(n-2);
return Fi[n];
//return Fi[n] = fi(n-1) + fi(n-2); 可以直接这样写！
}
int main()
{
int n;
cin >> n;
dp[1] = 1,dp[2] = 1;
for(int i=3; i<=n; i++) dp[i] = dp[i-1] + dp[i-2];
cout<<"dp = "<<dp[n]<<endl;
cout<<"记忆化搜索为 = "<<fi(n)<<endl;
return 0;
}
记忆化搜索实战！ 及两种写法！
洛谷P1434 [SHOI2002]滑雪
//记忆化搜索时f[N],可以初始化为-1，排除答案为0时候的干扰！
//由于递减肯定不会搜到重复点，不需要标记数组!
#include<iostream>
#include<cstring>
using namespace std;
const int N = 309;
int a[N][N],f[N][N];
int n,m;
const int dx[] = {-1,0,0,1};
const int dy[] = {0,1,-1,0};
int ans;
int dfs(int x,int y)
{
int nowx,nowy;
if(f[x][y]) return f[x][y];
f[x][y] = 1;
for(int i=0; i<4; i++)
{
nowx = x + dx[i];
nowy = y + dy[i];
if(nowx>=1 && nowx <=n && nowy >=1 && nowy <=m && a[nowx][nowy] < a[x][y])
{
f[x][y] = max(f[x][y],dfs(nowx,nowy)+1); //f[x][y] 维护最大值！
//dfs(nowx,nowy);
//f[x][y] = max(f[x][y],f[nowx][nowy]+1); //也可以这样写！
}
}
return f[x][y]; //返回值给上一层用；
}
int main()
{
ios_base :: sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m;
ans = 1;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++) cin >> a[i][j];
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
ans = max(ans,dfs(i,j));
}
}
cout<<ans<<endl;
return 0;
}
洛谷P4017 最大食物链计数;
1 无回溯条件！
#include<iostream>
#include<cstring>
using namespace std;
const int N = 3e6+9;
const int mod = 80112002;
int idx,e[N],ne[N],h[N];
int in[N],f[N];
void add(int a,int b)
{
e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
int n,m;
int dfs(int u)
{
if(f[u]) return f[u];
f[u] = 1; //由于无回溯条件所以f[u]置为1；
int sum = 0;
for(int i=h[u]; i!=-1; i=ne[i])
{
int j = e[i];
sum = (sum + dfs(j)) % mod;
f[u] = sum;
}
return f[u];
}
int main()
{
ios_base :: sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
memset(h,-1,sizeof h);
cin >> n >> m;
for(int i=1; i<=m; i++)
{
int a,b;
cin >> a >> b;
add(a,b);
in[b]++;
}
int ans = 0;
for(int i=1; i<=n; i++)
{
if(in[i] == 0) ans = (ans + dfs(i))%mod;
}
cout<<ans<<endl;
return 0;
}
2 有回溯条件！
#include<iostream>
#include<cstring>
using namespace std;
const int mod = 80112002;
const int N = 3e6+9;
int ne[N],e[N],h[N],idx;
int n,m;
int f[N];
int in[N],out[N];
void add(int a,int b)
{
e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
int dfs(int u)
{
if(out[u] == 0) return 1;
int sum = 0;
if(f[u]) return f[u];
for(int i=h[u]; i!=-1; i=ne[i])
{
int j = e[i];
sum = (sum + dfs(j))%mod;
}
f[u] = sum % mod;
return f[u];
}
int main()
{
int ans = 0;
memset(h,-1,sizeof h);
scanf("%d%d",&n,&m);
for(int i=1; i<=m; i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
b[in]++;
out[a]++;
}
for(int i=1; i<=n; i++)
{
if(!in[i])
{
ans = (ans + dfs(i)) % mod;
}
}
printf("%d\n",ans);
return 0;
}
acwing 2716. 食物链
//注意单个点不算食物链！
#include<iostream>
#include<cstring>
using namespace std;
const int N = 3e6+9;
int ne[N],e[N],h[N],idx;
int n,m;
int f[N];
int in[N],out[N];
void add(int a,int b)
{
e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
int dfs(int u)
{
if(out[u] == 0) return 1;
int sum = 0;
if(f[u]) return f[u];
for(int i=h[u]; i!=-1; i=ne[i])
{
int j = e[i];
sum = sum + dfs(j);
}
f[u] = sum;
return sum;
//int dfs(int u) //也可以这样写
//{
// if(out[u] == 0) return 1;
// if(f[u]) return f[u];
// for(int i=h[u]; i!=-1; i=ne[i])
// {
// int j = e[i];
// f[u] += dfs(j);
// }
// return f[u];
//}
}
int main()
{
int ans = 0;
memset(h,-1,sizeof h);
scanf("%d%d",&n,&m);
for(int i=1; i<=m; i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
b[in]++;
out[a]++;
}
for(int i=1; i<=n; i++)
{
if(!in[i] && out[i]) //入度为0，但是出度不为0；因为从1跑到n，当不存在这个边时候也会返回1，所以加入限制条件再记忆化搜索！
{
ans += dfs(i);
}
}
printf("%d\n",ans);
return 0;
}
不记忆化搜索，普通的dfs两种写法！
//以洛谷P1434 [SHOI2002]滑雪为例：
第一种没有递归中点，限制条件再递归下去！
区别不大！可以dfs时候可以像bfs一样加一个step
#include<iostream>
#include<cstring>
using namespace std;
const int N = 309;
int a[N][N],vis[N][N];
int n,m;
const int dx[] = {-1,0,0,1};
const int dy[] = {0,1,-1,0};
int ans,res;
void dfs(int x,int y)
{
int nowx,nowy;
for(int i=0; i<4; i++)
{
nowx = x + dx[i];
nowy = y + dy[i];
if(!vis[nowx][nowy] && nowx>=1 && nowx <=n && nowy >=1 && nowy <=m && a[nowx][nowy] < a[x][y])
{
vis[nowx][nowy] = 1;
ans++;
//cout<<"nowx = "<<nowx<<" nowy = "<<nowy<<" ans="<<ans<<endl;
res = max(res,ans);
dfs(nowx,nowy);
ans--;
vis[nowx][nowy] = 0;
}
}
}
int main()
{
ios_base :: sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m;
ans = 1;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++) cin >> a[i][j];
}
res = 1;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
ans = 1;
dfs(i,j);
//cout<<"res = "<<res<<endl;
}
}
cout<<res<<endl;
return 0;
}
第二种主动判断递归的终点！
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
int n,m;
int vis[109][109],a[109][109];
int ans;
int dir[4][2] = {1,0,-1,0,0,1,0,-1};
bool check(int x,int y)
{
int nowx,nowy;
for(int i=0; i<4; i++)
{
nowx = x + dir[i][0];
nowy = y + dir[i][1];
if(nowx >= 1 && nowx <= n && nowy >= 1 && nowy <= m)
{
if(!vis[nowx][nowy] && a[nowx][nowy] < a[x][y]) return true;
}
}
return false;
}
void dfs(int x,int y,int step)
{
if(!check(x,y))
{
ans = max(ans,step);
return;
}
for(int i=0; i<4; i++)
{
int xx,yy;
xx = x+dir[i][0];
yy = y + dir[i][1];
if(xx <= n && xx >= 1 && yy <= m && yy >= 1)
{
if(!vis[xx][yy] && a[xx][yy] < a[x][y])
{
vis[xx][yy] = 1;
dfs(xx,yy,step+1);
vis[xx][yy] = 0;
}
}
}
}
int main()
{
cin >> n >> m;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++) cin >> a[i][j];
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
vis[i][j] = 1;
dfs(i,j,1);
vis[i][j] = 0;
}
}
printf("%d\n",ans);
return 0;
}
acwing 2067 走方格
//普通TLE版暴搜！
#include<iostream>
#include<cstring>
using namespace std;
const int N = 100;
int n,m;
int f[N][N],ans;
const int dx[] = {1,0};
const int dy[] = {0,1};
void dfs(int x,int y)
{
if(x == n && y == m)
{
ans++;
return;
}
for(int i=0; i<2; i++)
{
int xx = x + dx[i];
int yy = y + dy[i];
if(xx <= n && xx >= 1 && yy <= m && yy >= 1)
{
if(xx % 2 != 0 || yy % 2 != 0) dfs(xx,yy);
}
}
}
int main()
{
ios_base :: sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m;
dfs(1,1);
cout<<ans<<endl;
return 0;
}
//记忆化搜索
#include<iostream>
#include<cstring>
using namespace std;
const int N = 100;
int n,m;
int f[N][N],ans;
const int dx[] = {1,0};
const int dy[] = {0,1};
int dfs(int x,int y)
{
if(x == n && y == m) return 1;
if(f[x][y]) return f[x][y];
//f[x][y] = 1;
for(int i=0; i<2; i++)
{
int xx = x + dx[i];
int yy = y + dy[i];
if(xx & 1 || yy & 1)
{
if(xx <= n && xx >= 1 && yy <= m && yy >= 1)
f[x][y] += dfs(xx,yy);
}
}
return f[x][y];
}
int main()
{
ios_base :: sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m;
//vis[1][1] = 1;
cout<<dfs(1,1)<<endl;
return 0;
}
京公网安备 11010502036488号