Mnemonic search

Memory search

In the afternoon, I was confused to see the minimum path repeatable path coverage of the directed graph

skiing

It's comfortable to go through it again , Define the array and dfs The definition of

/*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] From (i,j) How many steps can you expand outward at the beginning , Avoid repeated searches , Faster search  
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 return (i,j) Corresponding s Value  
		}
	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

I can't write in half , The answer indicates too many states

/*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];// From (sx,sy) To (i,j) Use k Total number of paths in steps  
int dx[]={
    -1,0,1,0};
int dy[]={
    0,1,0,-1};
void dfs(int x,int y,int step)// Control the number of steps  
{
    
	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];
}

The changed code , It shouldn't be a memory search , Search and pruning

/*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)// Control the number of steps  
{
    
	if(x==ex&&y==ey&&!step)ans++;
	if(!step)return ;
	if(abs(x-ex)+abs(y-ey)>step)return; // Without this paper cutting can only 50 branch 
	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 Water problem

/*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)// Record all w[1~20][1~20][1~20] Range of values  
{
    
	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));
	}
	
}

Pyramids use memory to write intervals 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)// It's equivalent to a cycle dp Enumerate the left and right endpoints  
{
    
    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);// Initialize the memorized array  
	solve(1,n);
	cout<<f[1][n];
	
}