搜索题简记

Luogu P1434 滑雪

dfs搜索

#include<bits/stdc++.h>

using namespace std;

inline int read(){
    int ans=0;
    char last=' ',ch=getchar();
    while(ch>'9'||ch<'0') last=ch,ch=getchar();
    while(ch>='0'&&ch<='9') ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar();
    if(last=='-') ans=-ans;
    return ans;
}

int r,c;
int mp[110][110],dp[110][110];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

bool pan(int x,int y){
	return x>0&&y>0&&x<=r&&y<=c;
}

int dfs(int x,int y){
	if(x>r||y>c||x<1||y<1) return 0;
	if(dp[x][y]!=-1) return dp[x][y];
	int ans=1;
	for(int i=0;i<4;i++){
		int xx=x+dx[i],yy=y+dy[i];
		if(pan(xx,yy)&&mp[xx][yy]<mp[x][y]){
			ans=max(ans,dfs(xx,yy)+1);
		}
	}
	dp[x][y]=ans;
	return ans;
}

bool pand(int i,int j){
	return mp[i][j]>=mp[i-1][j]&&mp[i][j]>=mp[i][j-1]&&mp[i][j]>=mp[i][j+1]&&mp[i][j]>=mp[i+1][j];
}

int main(){
	int b,Ans=0;
	r=read();c=read();
	for(int i=1;i<=r;i++)
		for(int j=1;j<=c;j++)
			mp[i][j]=read();
	for(int i=1;i<=r;i++)
		for(int j=1;j<=c;j++)
			if(pand(i,j)) {
				memset(dp,-1,sizeof(dp));
				b=dfs(i,j);
				Ans=max(b,Ans);
			}
	cout<<Ans<<endl;
    return 0;
}

Luogu P2383 狗哥玩木棒

剪枝：

1.所有木棒的长度和(sum/4)为整数

2.每根木棒的长度不大于(sum/4)

所有木棒拼接完成时(l1=l2=l3=l4)即为可行，否则不可行

#include<bits/stdc++.h>

using namespace std;

int n,m,a[30],sum;

bool dfs(int t,int l1,int l2,int l3,int l4) {
    if(t==m+1)
		return (l1==l2&&l2==l3&&l3==l4);
	if(l1>(sum/4)||l2>(sum/4)||l3>(sum/4)||l4>(sum/4))
		return 0;
    if(dfs(t+1,l1+a[t],l2,l3,l4)) 
		return 1;
    if(dfs(t+1,l1,l2+a[t],l3,l4)) 
		return 1;
    if(dfs(t+1,l1,l2,l3+a[t],l4)) 
		return 1;
    if(dfs(t+1,l1,l2,l3,l4+a[t])) 
		return 1;
    return 0;
}

int main() {
	scanf("%d",&n);
	while(n--) {
		scanf("%d",&m);
		sum=0;
		for(int i=1;i<=m;i++)
			scanf("%d",&a[i]),sum+=a[i];
		if(sum%4!=0)
			printf("no
");
		else {
			int flag=dfs(1,0,0,0,0);
			if(flag) 
				printf("yes
");
			else 
				printf("no
");
		}
	}
	return 0;
}