复建了一些水题，主要是深入浅出进阶篇的一些东西。我突然发现高中那会就没怎么练过搜索，上大学这样可不行！
水题，但是不影响我糖
我们注意到数据范围只有 $20$， 数据范围很小，即使采取暴力dfs估计也没事，接下来第一个问题就是考虑怎么判断一个数是不是素数。
简单看了一下数据范围，采取如下方法即可，时间复杂度 $O(\sqrt{n})$
inline bool ispri(int x)
{
if(x==1)
{
return false;
}
for(int i=2;i*i<=x;i++)
{
if(x%i==0)
{
return false;
}
}
return true;
}
接下来通过dfs实现，如果找到了 $k$ 个数，这样就可以直接判断是否是素数，如果是累计答案。如果没找全 $k$ 个数字，继续进行dfs即可。
完整代码如下：
#include<bits/stdc++.h>
using namespace std;
inline int read(void)
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
{
f=-1;
}
ch=getchar();
}
while(ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
constexpr int maxn = 25;
int a[maxn];
inline bool ispri(int x)
{
if(x==1)
{
return false;
}
for(int i=2;i*i<=x;i++)
{
if(x%i==0)
{
return false;
}
}
return true;
}
int ans,n,k;
inline void dfs(int x,int cnt,int sum)
{
if(cnt==k+1)
{
if(ispri(sum))
{
ans++;
}
return;
}
for(int i=x;i<=n;i++)
{
dfs(i+1,cnt+1,sum+a[i]);
}
}
int main(void)
{
n=read(),k=read();
for(int i=1;i<=n;i++)
{
a[i]=read();
}
dfs(1,1,0);
cout<<ans<<endl;
return 0;
}
先说 $90$ 分做法，观察到数据范围很小，考虑直接dfs+剪枝优化。从老鼠所在的位置出发，挨个枚举奶酪，如果没被吃直接吃掉，然后在此状态下继续进行dfs。如果当前的方案明显不优（即超过了已有的最小路程）直接return即可，体现剪枝的思想。如果都吃完了，而且目前的路径明显更优，这样就可以统计答案了。
通常在深度搜索算法中，最应该注意的就是参数的设置，在此题目中包括：
出发的位置
已经吃了多少奶酪
已经走了多远
这样我们不难看出走到下一个点的时候参数如何迭代，但是我们要注意一件事情，依题意这道题没有回头路一说，我们可以用一个布尔型数组vis维护某个点是否被访问到。值得一提的是，我们要从老鼠当前所在的位置出发，去枚举每一个奶酪，即从哪个奶酪开始吃，这样类似于“一条路走到黑”，也就是直接计算从第 $i$ 个奶酪开始吃有没有合法方案。因此我们需要在回溯执行完毕之后恢复vis[i]=0，这样可以保持好后续的dfs操作不受影响。
完整代码如下：
#include<bits/stdc++.h>
using namespace std;
inline int read(void)
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
{
f=-1;
}
ch=getchar();
}
while(ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
constexpr int maxn = 20;
struct cheese
{
double x,y;
}a[maxn];
int n;
double dis[maxn][maxn];
inline double getDis(cheese a,cheese b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void init(void)
{
for(int i=0;i<=n;i++)
{
for(int j=0;j<=n;j++)
{
dis[i][j]=getDis(a[i],a[j]);
}
}
}
double ans=0x3f3f3f3f;
bool vis[maxn];
inline void dfs(int cur,int sum,double len)
{
if(len>=ans)
{
return;
}
if(sum==n)
{
ans=min(len,ans);
return;
}
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
// continue;
vis[i]=1;
dfs(i,sum+1,len+dis[cur][i]);
vis[i]=0;
}
// vis[i]=1;
// vis[i]=0;
}
}
int main(void)
{
n=read();
for(int i=1;i<=n;i++)
{
cin>>a[i].x>>a[i].y;
}
init();
a[0].x=0;
a[0].y=0;
dfs(0,0,0);
cout<<fixed<<setprecision(2)<<ans<<endl;
return 0;
}
然后你非常漂亮的 $TLE $ 了三个点……
主要还是因为常数大导致的，我们考虑状态压缩，我们知道，计算机中的一个数是由无数个 $0$ 和 $1$ 组成的，假设我们有 $5$ 块奶酪，可以用 $(11000)_2$ 表示前两块被吃了后三块没有。这样我们可以用 f[i][j] 表示在 i 状态（二进制）下，老鼠位于j点时走过的最短路程。那么这样写有什么优点呢？这样写相当于把所需要的数据提前预处理出来了，一定程度上节省了所需时间，就像库函数一样“踩在巨人的肩膀上摘苹果”。
完整代码如下：
#include<bits/stdc++.h>
using namespace std;
inline int read(void)
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
{
f=-1;
}
ch=getchar();
}
while(ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
constexpr int maxn = 20;
struct cheese
{
double x,y;
}a[maxn];
int n;
double dis[maxn][maxn];
inline double getDis(cheese a,cheese b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void init(void)
{
for(int i=0;i<=n;i++)
{
for(int j=0;j<=n;j++)
{
dis[i][j]=getDis(a[i],a[j]);
}
}
}
double ans=0x3f3f3f3f;
bool vis[maxn];
double f[1<<maxn][maxn];
inline void dfs(int cur,int sum,double len,int status)
{
if(len>=ans)
{
return;
}
if(sum==n)
{
ans=min(len,ans);
return;
}
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
// continue;
// vis[i]=1;
// dfs(i,sum+1,len+dis[cur][i]);
// vis[i]=0;
int nxtStatus = status+(1<<(i-1));
if(f[nxtStatus][i] and f[nxtStatus][i]<=len+dis[cur][i])
{
continue;
}
vis[i]=true;
f[nxtStatus][i]=len+dis[cur][i];
dfs(i,sum+1,len+dis[cur][i],nxtStatus);
vis[i]=false;
}
// vis[i]=1;
// vis[i]=0;
}
}
int main(void)
{
// freopen("P1433_10.in","r",stdin);
n=read();
for(int i=1;i<=n;i++)
{
cin>>a[i].x>>a[i].y;
}
init();
a[0].x=0;
a[0].y=0;
// dfs(0,0,0);
dfs(0,0,0,0);
cout<<fixed<<setprecision(2)<<ans<<endl;
return 0;
}