Update
思路
看到 ,钦定状压。
用 cost 数组转移,同时用 from 与 way 记录来路,暴力枚举每一种情况。
提交。咋TLE了?
这个算法不够快,还有提升空间。
由于方案任意,可以考虑每次枚举第一个物品时都取编号最小者,时间会有很大优化。然而TLE依旧。
开快读!TLE。
再看看哪里挂了?
涉及到二进制的题,一般不用 math 库中的 log2() 函数(因为其常数贼大),而是手动打 hash 表。
一般这个 hash 表可以利用费马小定理减小空间,见代码。
终于过了。
Code
#include <math.h> #include <stdio.h> typedef long long llt; typedef unsigned uint;typedef unsigned long long ullt; typedef bool bol;typedef char chr;typedef void voi; typedef double dbl; inline bol _min(ullt&a,ullt b){return(b<a)?a=b,true:false;} inline ullt time(int x1,int y1,int x2,int y2){return(llt)(x1-x2)*(x1-x2)+(llt)(y1-y2)*(y1-y2);} inline uint hash(uint a,uint b){return a*25+b;} ullt cost[16777220],T[30][30];uint from[16777220],way[16777220]; uint LOG[37]; int X[30],Y[30]; voi get(uint S) { if(!S){putchar('0');return;} get(from[S]); if(way[S]/25==way[S]%25)printf(" %d 0",way[S]/25+1);else printf(" %d %d 0",way[S]/25+1,way[S]%25+1); } int main() { uint n;register uint p,q; scanf("%d%d%u",X,Y,&n);for(uint i=1;i<=n;i++)scanf("%d%d",X+i,Y+i); for(uint i=0;i<=n;i++)for(uint j=0;j<=n;j++)T[i][j]=time(X[i],Y[i],X[j],Y[j]); for(uint i=1;i<=n;i++)for(uint j=1;j<=n;j++)T[i][j]+=T[0][i]+T[j][0]; const uint tp=1<<n; for(uint i=0;i<=30;i++)LOG[(1u<<i)%37]=i; for(register uint S=1;S<tp;S++) { p=S&-S;cost[S]=1145141919810llu; for(uint S2=S;S2;S2-=q) { q=S2&-S2; if(_min(cost[S],cost[S^(p|q)]+T[LOG[p%37]+1][LOG[q%37]+1])) from[S]=S^(p|q),way[S]=hash(LOG[p%37],LOG[q%37]); } } printf("%llu\n",cost[tp-1]),get(tp-1),putchar('\n'); return 0; }