糖果纯dfs做法
开始一看,这不是dfs吗,然后发现数据肯定会超时,就感觉能用贪心优化,可惜想不到。
看了题解都是状态压缩,关键咱也不会。
没事,能过50%的数据也是过,下面是dfs写法
#include<bits/stdc++.h>
using namespace std;
int hs[25];//哈希存口味
int Cd[105][25];//存储
int cnt=INT_MAX;//最终答案
int N,M,K;
void DFS(int n,int m,int x)//步长、种类数、索引
{
if(m==M) //种类满了
{
cnt =min(cnt,n); // 更新cnt的值
return;
}
if(x>=N) // 边界
return;
// 哈希表处理// 看看x索引下的种类数
for(int i=0;i<K;i++)
{
if(hs[Cd[x][i]]==0)
m++; // 种类变多
hs[Cd[x][i]]++;
}
DFS(n+1,m,x+1); // 纵向fs
// 反选
for(int i=0;i<K;i++)
{
hs[Cd[x][i]]--;
if(hs[Cd[x][i]]==0)
m--; //减掉一次就等于0,说明刚刚进入的支点让m变大了,捡回去
}
DFS(n,m,x+1); //横向dfs
}
int main()
{
cin >> N >> M >> K;
for(int i=0;i<N;i++)
{
for(int j=0;j<K;j++)
{
cin >> Cd[i][j];
}
}
DFS(0,0,0);
if(cnt>=N) //没有满足条件的值
cout << -1;
else
cout << cnt;
return 0;
}
还有一个写法,差不多
#include <bits/stdc++.h>
using namespace std;
const int N = 120, M = 30;
int Cd[N][M], hs[M], st[N], cnt = INT_MAX;
int n, m, k;
void Hash(int i, int &num)
{
for (int j = 1; j <= k; ++j) {
if (hs[Cd[i][j]] == 0) num++;
hs[Cd[i][j]]++;
}
}
void deHash(int i, int &num)
{
for (int j = 1; j <= k; ++j) {
if (hs[Cd[i][j]] == 1) num--;
hs[Cd[i][j]]--;
}
}
void dfs(int sp, int index, int num)
{
if (index >= n) return;
if (num >= m) {
cnt = min(cnt, sp);
return;
}
for (int i = index + 1; i <= n; i++)
{
if (st[i]) continue;
Hash(i, num);
st[i] = 1;
dfs(sp + 1, i, num);
deHash(i, num);
st[i] = 0;
}
}
int main()
{
cin >> n >> m >> k;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= k; ++j)
cin >> Cd[i][j];
dfs(0, 0, 0);
cout << (cnt == INT_MAX ? -1 : cnt) << endl;
}
本题的dfs也有难点,难点在于如何回溯,本题要采用一种反选的办法
一般