- 可行性剪枝
a)
|
样例输入 |
样例输出 |
|
5 3 |
axy |
代码：
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,b[30],lasy,lasf;
char c[30],a[30];
void dfs(int now,int x,int nowy,int nowf)
{
int t=0;
if(nowy<1) t+=1-nowy;
if(nowf<2) t+=2-nowf;
if(t+now>m || (nowy<1 && x>lasy) || (nowf<2 && x>lasf)) return;
if(now==m)
{
for(int i=1;i<=m;i++) printf("%c",a[i]);
printf(" ");
return;
}
if(x>n) return;
if(b[x])
{
a[now+1]=c[x];
dfs(now+1,x+1,nowy+1,nowf);
}
else
{
a[now+1]=c[x];
dfs(now+1,x+1,nowy,nowf+1);
}
dfs(now,x+1,nowy,nowf);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
char ch=getchar();
while(ch<'a' || ch>'z') ch=getchar();
c[i]=ch;
}
sort(c+1,c+n+1);
for(int i=1;i<=n;i++)
if(c[i]=='a' || c[i]=='e' || c[i]=='i' || c[i]=='o' || c[i]=='u') b[i]=1;
else b[i]=0;
for(int i=1;i<=n;i++)
if(b[i]) lasy=i;
else lasf=i;
dfs(0,1,0,0);
return 0;
}
- 当前最优解剪枝
a)
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<iostream>
#define N 110000
using namespace std;
double x[20],y[20],ans;
int n,cnt;
bool b[20];
double dis(int i,int j)
{
double t1=x[i]-x[j],t2=y[i]-y[j];
return sqrt(t1*t1+t2*t2);
}
void dfs(int x,double tmp)
{
if(ans>0 && tmp>=ans) return;
if(cnt==n)
{
ans=tmp;
return;
}
for(int i=1;i<=n;i++)
{
if(b[i]) continue;
cnt++;
b[i]=1;
dfs(i,tmp+dis(x,i));
cnt--;
b[i]=0;
}
}
int main()
{
scanf("%d",&n);
ans=-1;
for(int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]);
cnt=0;
dfs(0,0);
printf("%.2lf ",ans);
return 0;
}
- 记忆化搜索
a) Function：
i. 洛谷p1464
ii. 代码：