社区讨论

初学递归搜索,10分求助!(目标30分)

P5017[NOIP 2018 普及组] 摆渡车参与者 3已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@locvt88s
此快照首次捕获于
2023/10/30 20:34
2 年前
此快照最后确认于
2023/11/05 07:04
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
const int NR=25;
int t[NR],maxx;
int n,m;
int a[111];
int ans=999999;
int cal()
{
    int sum=0;
    for(int i=1;i<=maxx;i++){
    	if(a[i]==0&&a[i+1]==0)return 1e9;
    	if(a[i]==1&&a[i+1]==1)return 1e9;
    	if(a[i]==1){
    		for(int j=0;j<n;j++){
    			if(t[j]==i)sum++;
    		}
    	}
    }
    return sum;	
}

void dfs(int step)
{
	if (step > maxx)
	{
		ans = min(ans, cal());
		return;
	}
	a[step] = 0;
	dfs(step + 1);
	a[step] = 1;
	dfs(step + 1);
}

int main(){
	
	cin>>n>>m;
	if(m==1){
		cout<<0;
		return 0;
	}
	if(m==2){
		for(int i=0;i<n;i++){
			cin>>t[i];
			maxx=max(maxx,t[i]);
		}
		
		dfs(1);
		cout<<ans;
	}
	return 0;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...