记忆化搜索

记忆化搜索

下午看有向图的最小路径可重复径覆盖看懵了

滑雪

一遍过还是舒服的,明确数组的定义和dfs的定义即可

/*Love coding and thinking!*/ 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#define pb push_back 
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo2(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'

using namespace std;

typedef long long ll;
const int N=110;
int a[N][N],s[N][N],n,m;
//s[i][j]表示从(i,j)开始能向外扩展多少步,避免了重复搜索，加快了搜索速度 
int dx[]={
    -1,0,1,0};
int dy[]={
    0,1,0,-1};
int dfs(int x,int y)
{
    
	if(s[x][y])return s[x][y];
	s[x][y]=1;
	for(int i=0;i<4;i++)
	{
    
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(nx<1||nx>n||ny<1||ny>m)continue;
		if(a[nx][ny]>=a[x][y])continue;
		s[x][y]=max(s[x][y],dfs(nx,ny)+1);
	}	
	return s[x][y];
}

int main()
{
    
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
    
			if(!s[i][j])
				s[i][j]=dfs(i,j);//dfs返回(i,j)对应的s的值 
		}
	int ans=-1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
    
			ans=max(ans,s[i][j]);
		}
	cout<<ans;
	return 0;
}

Cow Travelling S

写到一半不会写了,答案表示的状态太多了

/*Love coding and thinking!*/ 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#define pb push_back 
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo2(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'

using namespace std;

typedef long long ll;
const int N=110;
int n,m,k;
char a[N][N];
int sx,sy,ex,ey;
int cnt[N][N][16];//表示从(sx,sy)到(i,j)使用k步的路径总数 
int dx[]={
    -1,0,1,0};
int dy[]={
    0,1,0,-1};
void dfs(int x,int y,int step)//控制步数 
{
    
	if(cnt[x][y])return cnt[x][y];
	for(int i=0;i<4;i++)
	{
    
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(nx<1||nx>n||ny<1||ny>m)continue;
		if(a[nx][ny]=='*')continue;
		cnt[nx][ny]
	}
	
	return cnt[x][y];
}

int main()
{
    
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf(" %c",&a[i][j]);
	cin>>sx>>sy>>ex>>ey;
	dfs(sx,sy,k);
	cout<<cnt[ex][ey][k];
}

改动之后的代码,不应该算是记忆化搜索，就是搜索加剪枝

/*Love coding and thinking!*/ 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#define pb push_back 
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo2(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'

using namespace std;

typedef long long ll;
const int N=110;
int n,m,k;
char a[N][N];
int sx,sy,ex,ey;
int ans;
int dx[]={
    -1,0,1,0};
int dy[]={
    0,1,0,-1};

void dfs(int x,int y,int step)//控制步数 
{
    
	if(x==ex&&y==ey&&!step)ans++;
	if(!step)return ;
	if(abs(x-ex)+abs(y-ey)>step)return; //没有这个剪纸只能50分
	for(int i=0;i<4;i++)
	{
    
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(nx<1||nx>n||ny<1||ny>m)continue;
		if(a[nx][ny]=='*')continue;
		dfs(nx,ny,step-1);	
	}
}

int main()
{
    
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf(" %c",&a[i][j]);
	cin>>sx>>sy>>ex>>ey;
	dfs(sx,sy,k);
	cout<<ans;
}

Function水题

/*Love coding and thinking!*/ 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#define pb push_back 
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo2(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;
const int N=30;
typedef long long ll;
ll a,b,c;
ll f[N][N][N];
ll w(int a,int b,int c)//记录所有的w[1~20][1~20][1~20]的值域 
{
    
	if(a<=0||b<=0||c<=0)return 1;
	if(a>20||b>20||c>20)return w(20,20,20);
	if(f[a][b][c]!=-1)return f[a][b][c];
	else
	{
    
		if(a<b&&b<c)
			return f[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
		else
			return f[a][b][c]=w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);
	}
}

int main()
{
    
	mem(f,-1);
// freopen("1.txt","r",stdin);
	while(cin>>a>>b>>c)
	{
    
		if(a==-1&&b==-1&&c==-1)break;
		printf("w(%lld, %lld, %lld) = %lld\n",a,b,c,w(a,b,c));
	}
	
}

金字塔利用记忆化写区间dp

/*Love coding and thinking!*/ 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#define pb push_back 
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo2(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;

typedef long long ll;
const int N=310,mod=1e9;
int f[N][N];

int solve(int l,int r)//相当于循环dp里枚举左右端点 
{
    
    if(l>r)return 0;
    if(l==r)return 1;
    if(f[l][r]!=-1)return f[l][r];
    for(int k=l;k<r;k+=2)
    {
    
        f[l][r]=(f[l][r]+1ll*solve(l,k)*solve(k+1,r-1))%mod;
    }
    return f[l][r];
}

int main()
{
    
	string s;cin>>s;	
	memset(f,-1,sizeof f);//初始化记忆化数组 
	solve(1,n);
	cout<<f[1][n];
	
}