Hie with the Pie poj-3311

　　　　題目大意：n+1個點，偽旅行商問題。

　　　　注釋：n<=10。

　　　　　　想法：咳咳，第一道狀壓dp，下面我來介紹一下狀壓dp。

　　　　　　　　所謂dp，就是動態性決策規劃，通過上一時刻或上幾時刻的狀態來更新當前狀態并且無后效性。而狀壓dp就是將之前的狀態通過二進制表現出來。幾個例子。有五個格子_ _ _ _ _。上面可以放棋子或者不放。我們將放棋子的格子標注為1，不放棋子的格子標注為0。那么，我們就可以用一個二進制數來表達出人任何一個的完整狀態而不是片面的，這就是狀壓dp。但是由于我們需要表示出所有的狀態，所以狀壓dp的空間復雜度是指數級的，這就比較的傷心。所以看見題目的數據范圍有那么一個小的可憐的，可以考慮考慮狀壓dp。狀壓dp前置知識點是位運算，在此不做介紹。

　　　　　　關于這道題，我們設dp[s][i]。表示s這個狀態的最小代價，且這個狀態最后到達的點是i。之后轉移就是枚舉s的上一個到達的點。在此，我們要注意，題目中給出的是鄰接矩陣的形式，我們先用floyd求出兩點之間的最短路，之后通過上一個到達的點的狀態加上dis[j][i]來更新當前狀態。

　　　　最后，附上丑陋的代碼... ...

#include <iostream> #include <cstdio> #include <cstring> #define inf 0x3f3f3f3f using namespace std; int dp[5000][20]; int map[20][20]; int main() {int n;while(1){memset(map,0x3f,sizeof(map));memset(dp,0,sizeof(dp));scanf("%d",&n);if(!n) return 0;for(int i=0;i<=n;i++){for(int j=0;j<=n;j++){scanf("%d",&map[i][j]);}}for(int k=0;k<=n;k++)//floyd{for(int i=0;i<=n;i++){for(int j=0;j<=n;j++){map[i][j]=min(map[i][j],map[i][k]+map[k][j]);}}}for(int S=0;S<=(1<<n)-1;S++)//枚舉所有狀態{for(int i=1;i<=n;i++)//考慮最后到達的點{if(S&(1<<(i-1)))//現判斷i是不是s中已經到達的點{ if(S==(1<<(i-1)))//特判，如果s只到達過i{dp[S][i]=map[0][i];}else{dp[S][i]=inf;for(int j=1;j<=n;j++){if(S&(1<<(j-1))&&(j!=i)){dp[S][i]=min(dp[S^(1<<(i-1))][j]+map[j][i],dp[S][i]);}}}}}}int ans=inf;for(int i=1;i<=n;i++)//最后所有的點全部都到達后，枚舉最后到達的點去統計答案。{ans=min(ans,dp[(1<<n)-1][i]+map[i][0]);}printf("%d\n",ans);} }

?

　　小結：題目中明確指出所給的鄰接矩陣可能不是對稱的，容易在floyd時將其按照對稱處理。

轉載于:https://www.cnblogs.com/ShuraK/p/8468050.html

總結

以上是生活随笔為你收集整理的Hie with the Pie的全部內容，希望文章能夠幫你解決所遇到的問題。

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