題目鏈接：點擊查看

題目大意：給出一個 $n?m$ 的數字矩陣，現在可以對 行 進行重新排列，現在對排列后的矩陣按列展開成線性：$s_1,s_2,\dots ,s_{nm}=maz{e}_{1,1}，maz{e}_{2,1}，...maz{e}_{n,1}，maz{e}_{2,1}，...，maz{e}_{n,m}$

現在需要找到一個最大的 k，滿足 s 數組中所有相鄰元素的絕對值之差都大于等于 k

題目分析：因為 n 很小，所以考慮狀壓，當然不能普通的狀壓，不難看出我們需要按照某個順序將 n 行都走一遍，這個與哈密頓通路的模型剛好契合，所以考慮哈密頓通路

考慮如果任意兩行 i 和 j 如果相鄰的話，那么其 k 值就是${\min }_{t=1}^m(|maz{e}_{i,t}?maz{e}_{j,t}|)$，這個可以作為行 i 到行 j 的邊權

當然上面的情況是沒有考慮首尾，如果涉及到首尾的話還需要考慮跨行的情況，此時 i 作為第一行，j 作為最后一行時的 k 值就是 ${\min }_{t=2}^m(|maz{e}_{i,t?1}?maz{e}_{j,t}|)$

如此一來直接跑哈密頓通路即可，期間維護一下所有狀態中沿途路徑最小值的最大值便是答案

在轉移時可以無需考慮首尾的情況，最后更新答案的時候再一并更新就好了

代碼：

// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #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> #include<cassert> #include<bitset> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e4+100;int maze[20][N],dp[(1<<16)+100][20][20],d[20][20],dd[20][20];//d是不計首尾的最短路,dd是計首尾的最短路int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m;scanf("%d%d",&n,&m);for(int i=0;i<n;i++)for(int j=1;j<=m;j++)scanf("%d",&maze[i][j]);if(n==1)//特判只有一行{int ans=inf;for(int i=2;i<=m;i++)ans=min(ans,abs(maze[0][i]-maze[0][i-1]));printf("%d\n",ans);return 0;}for(int i=0;i<n;i++)for(int j=0;j<n;j++){if(i==j)continue;d[i][j]=dd[i][j]=inf;for(int k=1;k<=m;k++)d[i][j]=min(d[i][j],abs(maze[i][k]-maze[j][k]));for(int k=2;k<=m;k++)dd[i][j]=min(dd[i][j],abs(maze[i][k-1]-maze[j][k]));}for(int i=0;i<n;i++)dp[1<<i][i][i]=inf;for(int s=0;s<1<<n;s++)for(int i=0;i<n;i++)//起點for(int j=0;j<n;j++)//終點for(int k=0;k<n;k++)//下一次的終點{if(((s>>i)&1)==0)continue;if(((s>>j)&1)==0)continue;if(((s>>k)&1)==1)continue;dp[s|(1<<k)][i][k]=max(dp[s|(1<<k)][i][k],min(dp[s][i][j],d[j][k]));}int ans=0;for(int st=0;st<n;st++)for(int ed=0;ed<n;ed++)ans=max(ans,min(dp[(1<<n)-1][st][ed],dd[st][ed]));printf("%d\n",ans);return 0; } 超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的CodeForces - 1102F Elongated Matrix(哈密顿路径+状压dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

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