P1433 吃奶酪——剪枝
原题目：P1433 吃奶酪
题目信息
第一反应是贪心，因为老鼠需要吃掉所有的奶酪，所以每次吃掉最近的应该是最优策略，于是贪心代码：
#include<iostream>
#include<iomanip>
#include<cmath>
#include<vector>
using namespace std;
struct point{
int x, y;
int used;
};
int currentp=0;
double res=0;
vector<point> v;
double dis(int x1,int y1,int x2,int y2){
return sqrt(pow((x1-x2),2)+pow((y1-y2),2));
}
double solve(point p){
double cur=9999999999;
for(int i=0;i<v.size();i++){
point temp = v[i];
if(temp.used) continue;
double d = dis(temp.x,temp.y,p.x,p.y);
if(d<cur){
cur=d;
currentp=i;
}
}
return cur;
}
int main(){
int n;
cin>>n;
point po;
po.x=0;po.y=0;po.used=1;
v.push_back(po);
for(int i=0;i<n;i++){
point p;
cin>>p.x>>p.y;
p.used=0;
v.push_back(p);
}
while(n>0){
res+=solve(v[currentp]);
v[currentp].used=1;
n--;
}
cout<<setiosflags(ios::fixed)<<setprecision(2)<<res<<endl;
return 0;
}
只能通过40%的数据，仔细思考了下，贪心并不是最优解，所以又来吧，我的递归搜索
#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;
double mindis = 99999999999;
double d[20][20];
struct point{
double x,y;
};
int vis[20];
double ans=0;
point p[20];
int n;
double dis(double x1,double y1,double x2,double y2){
return sqrt(pow((x1-x2),2)+pow((y1-y2),2));
}
void dfs(int cnt,int src){
if(ans>mindis)
return;
if(cnt==n){
mindis = min(mindis,ans);
return;
}
for(int i=0;i<=n;i++){
if(!vis[i]){
vis[i]=1;
ans+=d[src][i];
dfs(cnt+1,i);
vis[i]=0;
ans-=d[src][i];
}
}
}
int main(){
cin>>n;
p[0].x=0;p[0].y=0;vis[0]=1
for(int i=1;i<=n;i++){
cin>>p[i].x>>p[i].y;
}
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++){
if(i==j) continue;
d[i][j]=dis(p[i].x,p[i].y,p[j].x,p[j].y);
}
dfs(0,0);
cout<<setiosflags(ios::fixed)<<setprecision(2)<<mindis<<endl;
return 0;
}
}
这样其实是穷举+剪枝，复杂度应该在n!，不过n最大只有15,索性试一试，结果就是
过了90%的数据，看题解需要状压dp，orz 8会，dp这玩意想不到的就是想不到。对了，细节就是给的坐标可能会有小数，有一组样例是这样设计的。
