洛谷 AT_abc358_c [ABC358C] Popcorn 题解

本文主要是介绍洛谷 AT_abc358_c [ABC358C] Popcorn 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目翻译

在 AtCoder 乐园里，有 $N$ 个爆米花摊位，有 $M$ 种不同口味的爆米花，第 $i$ 种爆米花的编号为 $i$ 。

高桥知道每个摊位售卖的爆米花有哪些，用 $N$ 个长度为 $M$ 的字符串表示 $S$ ，若 $S_i$ 为：

o：说明这个摊位出售第 $i$ 种爆米花。
x：说明这个摊位不出售第 $i$ 种爆米花。

保证每个摊位至少出售一种爆米花，每种爆米花至少会在一个摊位中出售。

请问高桥最少去多少个摊位才能买到所有种类的爆米花。

题目分析

可以用 dfs 解决。

为了使高桥去的摊位尽可能小，这个摊位的所有种类的爆米花他肯定都要买（如果已经买了的可以不用），如果用字符串 $a$ 表示高桥可以买到的爆米花的种类，那么对于任意一个摊位，若 $S_i$ 为：

o：那么将 $a_i$ 设置为 o。
x：不进行改动。

当 $a$ 的全部字符都是 o 时就刷新一遍答案，最后输出即可。

Code

#include<iostream>
using namespace std;
int n,m,ans=10;
string str[10];
void dfs(int x,int num,string s) {//dfs 深搜if(x>=n) return;bool flag=true;string ss=s;for(int i=0;i<m;++i) {if(str[x][i]=='o') s[i]='o';if(s[i]=='x') flag=false;}if(flag) ans=min(ans,num+1);//刷新答案else dfs(x+1,num+1,s);//如果已经达成目标了就不需要继续去其他摊位dfs(x+1,num,ss);//如果不到这个摊位去买
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=0;i<n;++i) cin>>str[i];dfs(0,0,"xxxxxxxxxx");//初始要全部是xcout<<ans;return 0;
}