題目鏈接：點擊查看

題目大意：給出一個 n * m 的二維平面，其中有 k 個紙片，給出第一個紙片的位置，要求從第一個紙片出發，經過每個紙片一次后再回到第一個紙片的位置，輸出最短路徑

題目分析：最短哈密頓路徑的模板題，比賽的時候為什么沒看出來呢。。好像是被 n * m 很小所迷惑了，感覺像是一道搜索題，但想了半天沒什么思路就不想做了，賽后回顧一下的時候發現，k 給的特別小，最大只有 11 ，而且題目的條件又完全符合哈密頓路徑的性質，只不過要求起點和終點重合，那么我們只需要最后對每個狀態維護一下到起點的最小值就好了

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;struct Point {int x,y; }point[15];int d[15][15],dp[(1<<11)+100][15];int dis(int x,int y) {return abs(point[x].x-point[y].x)+abs(point[x].y-point[y].y); }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){int n,m;scanf("%d%d",&n,&m);scanf("%d%d",&point[0].x,&point[0].y);int k;scanf("%d",&k);for(int i=1;i<=k;i++)scanf("%d%d",&point[i].x,&point[i].y);for(int i=0;i<=k;i++)for(int j=0;j<=k;j++)d[i][j]=dis(i,j);memset(dp,inf,sizeof(dp));dp[1][0]=0;for(int i=0;i<(1<<k+1);i++)for(int j=0;j<=k;j++){if(dp[i][j]==inf)continue;if((i>>j)&1){for(int t=0;t<=k;t++){if((i>>t)&1)continue;dp[i|(1<<t)][t]=min(dp[i|(1<<t)][t],dp[i][j]+d[j][t]);}}}int ans=inf;for(int i=0;i<=k;i++)ans=min(ans,dp[(1<<k+1)-1][i]+d[0][i]);printf("The shortest path has length %d\n",ans);}return 0; }

?

總結

以上是生活随笔為你收集整理的牛客 - 收集纸片(最短哈密顿路径-状压dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。