2024-01-17竞赛笔记

2024/1/17

广度优先搜索 BFS 学习笔记 - XiaoQuQu

深度优先搜索 DFS 学习笔记 - XiaoQuQu

//P2392 kkksc03考前临时抱佛脚
#include<bits/stdc++.h>
using namespace std;
int a[5000][10000];
int sum,ans,lft,rght;
int s[5000];
void dfs(int x,int dep)//x表示第几个科目,dep表示第几题
{
	if(dep>s[x])
	{
		sum=min(sum,max(lft,rght));
		return;
	}
	lft+=a[x][dep];//左脑尝试
	dfs(x,dep+1);
	lft-=a[x][dep];//回溯
	rght+=a[x][dep];//右脑
	dfs(x,dep+1);
	rght-=a[x][dep];//回溯 
 } 
int main()
{
	for(int i=1;i<=4;i++)
		cin>>s[i];
	for(int i=1;i<=4;i++)//科目
	{
		sum=INT_MAX;
		for(int j=1;j<=s[i];j++)//题目
			cin>>a[i][j];//每题耗时
		dfs(i,1);
		ans+=sum;//sum有该科目完成的最小耗时，统计进ans
		 
	 } 
	 cout<<ans<<endl;
	 return false;
}

//P1025 [NOIP2001 提高组] 数的划分--递归做法 
#include<bits/stdc++.h>
using namespace std;
int l,k;
int se(int n,int k,int min){
	if(k==1) return n>=k;
	else 
	{
		int s=0;
		for(int i=min;i<=n/k;i++)
		{
			s+=se(n-i,k-1,i);
		}
		return s;
	}
}
int main(){
	cin>>l>>k;
	cout<<se(l,k,1);
	return 0;
}

//P2404	自然数的拆分问题
#include<bits/stdc++.h>
using namespace std;
int a[10001]={1},n,total;
void print(int t)
{

	for(int i=1;i<=t;i++)//拆分方案 
	{
		if(i!=t) cout<<a[i]<<"+";
		else cout<<a[i]<<endl;
	}

}
void se(int s,int t)
{
	for(int i=a[t-1];i<=s;i++)
	{
		if(i<n){//i要大于等于前一位数,且不超过n
			a[t]=i;//保存结果
			s-=i;//继续拆分
			if(s==0) print(t) ;//拆分结束，输出
			else se(s,t+1);//继续搜索
			s+=i;//回溯：加上拆分的数 
		}
	}
}
int main()
{
	cin>>n;
	se(n,1);
}