DFS day01 上午 作业答案
2025-01-21 09:47:11
发布于：上海
40阅读
0回复
0点赞
撤硕管理员
// 100
// i n/i
// 2 50
// 4 25
// 10 10
// 25 4
// 50 2
// O(x) -》 O(sqrt(x));
#include<bits/stdc++.h>
using namespace std;
int n;
int a[20];
//id同学编号
bool is_prime(int x){
if(x<=1)return false;
for(int i=2;i<=x-1;i++){
if(x%i==0){
return false;
}
}
return true;
}
int ans = 0;
void dfs(int id,int sum){
if(id==n+1){
if(is_prime(sum))ans++;
return;
}
//选择他上厕所
sum+=a[id];
dfs(id****um);
//不选择他上厕所
sum-=a[id];
dfs(id****um);
}
// 1e8
// 2^12 = 4096
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
dfs(1,0);
cout<<ans;
return 0;
}
分开午休
#include<bits/stdc++.h>
using namespace std;
int a[30];
int n;
int ans = 1e9;
void dfs(int id,int suma,int sumb){
if(id==n+1){
ans = min(ans,max(suma,sumb));
return;
}
suma+=a[id];
dfs(id****uma,sumb);
sumb+=a[id];
suma-=a[id];//回溯
dfs(id****uma,sumb);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
dfs(1,0,0);
cout<<ans;
return 0;
}
爆米花
#include<bits/stdc++.h>
using namespace std;
const int N = 15;
string s[N];
int kowei[N];//每种口味选了多少次
int ans = 1e9;
int n,m;
void dfs(int id,int sum){
if(id==n+1){
bool st = true;
for(int i=0;i<m;i++)if(kowei[i]==0)st=false;
if(st)ans=min(ans,sum);
return;
}
//选
for(int i=0;i<m;i++){
if(s[id][i]=='o')kowei[i]++;
}
dfs(id****um+1);
for(int i=0;i<m;i++){
if(s[id][i]=='o')kowei[i]--;
}
//不选
dfs(id****um);
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>s[i];
}
dfs(1,0);
cout<<ans;
return 0;
}
有帮助，赞一个