本文主要是介绍SDUT 3061 聪明的玛雅 （状压DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目地址：SDUT 3061
这题的比赛的时候的后台数据是错的。。。好坑啊。。。。就不吐槽出题人了。。
比赛的时候我的思路是错的，漏考虑了一种情况。应该把所有状态下的最短距离都要求出来，而我当时的思路是按照前面能选两个则选两个的贪心思路来状压，但是有的时候可以最多走奇数个并且没全走完，这种情况下就不对了。
正确思路是每次找两个没走过的状态，分成选一个和选两个两种情况来DP。然后最后找所有状态中经过的个数最多的并且距离最短的即可。对于每种状态下经过多少个，可以预处理。
代码如下：
#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <stdio.h>
using namespace std;
const double INF=1e9;
const double eqs=1e-5;
int b[1<<17];
double dp[1<<17];
struct node {int x, y;
} fei[32];
double dist(node f1, node f2)
{return sqrt((f1.x-f2.x)*(f1.x-f2.x)*1.0+(f1.y-f2.y)*1.0*(f1.y-f2.y));
}
void init(int n, int tot)
{int i, j;memset(b,0,sizeof(b));for(i=1; i<tot; i++) {for(j=0; j<n; j++) {if(i&(1<<j)) {b[i]++;}}dp[i]=INF;}
}
int main()
{int n, t, v, max1, tmp, i, j, k, tmp1, tot;node st;st.x=st.y=0;while(scanf("%d%d%d",&n,&v,&t)!=EOF) {for(i=0; i<n; i++) {scanf("%d%d",&fei[i].x,&fei[i].y);}tot=1<<n;init(n,tot);dp[0]=0;for(i=0; i<tot; i++) {for(j=0; j<n; j++) {if((i&(1<<j))==0) {tmp=i+(1<<j);dp[tmp]=min(dp[tmp],dp[i]+2*dist(st,fei[j]));for(k=j+1; k<n; k++) {if((tmp&(1<<k))==0) {tmp1=tmp+(1<<k);dp[tmp1]=min(dp[tmp1],dp[i]+dist(st,fei[j])+dist(st,fei[k])+dist(fei[j],fei[k]));}}}}}double d;d=t*v*1.0;//printf("%d\n",d);int max1=-1;double t, min_d=INF;for(i=1; i<tot; i++) {if(dp[i]-d>eqs) continue ;if(max1<b[i]) {max1=b[i];min_d=dp[i];} else if(max1==b[i]) {if(min_d>dp[i]) min_d=dp[i];}}t=min_d/v;printf("%d %.2f\n",max1,t);}return 0;
} 这篇关于SDUT 3061 聪明的玛雅 （状压DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
