傳送門

題意：給出$N$個數和一個長為$M$、所有數在$[1,N]$范圍之內的正整數序列$a_i$，求出這$N$個數的一種排列$p_1...p_N$使得$\sum\limits_{i=2}^M |p_{a_i}-p_{a_{i-1}}|$最小。$N \leq 20,M \leq 1000$

---

?$N \leq 20$給了我們很明顯的狀壓DP的信息，但是DP方程的思維難度還是有點大。

我們考慮按照數字從小到大地指定它在$p_i$中的位置。這樣我們可以通過預處理某一個位置在$a_i$中相鄰位置的數字的情況得到這一個數的貢獻（也就是可以直接把絕對值符號拆開來計算它的貢獻），這樣子轉移就會方便很多了。

設$f_i$表示已經指定了數字的序列$p$中的元素集合為$i$(eg.$i=10101$就表示指定了$p_1,p_3,p_5$，而$i=01011$表示指定了$p_1,p_2,p_4$)，且對應的數為$N$個數中最小的若干個時，最小的難度值為多少。我們可以預處理$g_{i,j}$表示在序列$a$中與$i$相鄰的且在集合$j$中的數的出現次數的總和(eg.如果有某一對相鄰的數對為$2,3$，那么$g_{2,2^3}++,g_{3,2^2}++$)，這樣我們轉移的時候只需要取$g_{k,i}-g_{k,2^N - 1 \, xor \, i}$就可以得到這一個數的貢獻（也就是拆了絕對值之后的系數）。然后枚舉轉移點轉移即可。

看到絕對值就要考慮一下從小到大然后拆掉絕對值符號算貢獻呢qwq

1 #include<bits/stdc++.h> 2 using namespace std; 3 4 int now[21] , dp[1 << 21] , cnt[21][1 << 21] , cnt1[1 << 21] , N , M; 5 6 inline int lowbit(int x){ 7 return x & -x; 8 } 9 10 int main(){ 11 cin >> N >> M; 12 for(int i = 0 ; i < N ; i++) 13 cin >> now[i]; 14 int last = -1; 15 while(M--){ 16 int x; 17 cin >> x; 18 x--; 19 if(last != -1){ 20 cnt[last][1 << x]++; 21 cnt[x][1 << last]++; 22 } 23 last = x; 24 } 25 memset(dp , 0x3f , sizeof(dp)); 26 dp[0] = 0; 27 sort(now , now + N); 28 for(int i = 1 ; i < 1 << N ; i++) 29 for(int j = 0 ; j < N ; j++) 30 cnt[j][i] = cnt[j][i - lowbit(i)] + cnt[j][lowbit(i)]; 31 for(int i = 1 ; i < 1 << N ; i++){ 32 cnt1[i] = cnt1[i - lowbit(i)] + 1; 33 for(int j = 0 ; j < N ; j++) 34 if(i & (1 << j)) 35 dp[i] = min(dp[i] , dp[i ^ (1 << j)] + (cnt[j][i] - cnt[j][(1 << N) - 1 - i]) * now[cnt1[i] - 1]); 36 } 37 cout << dp[(1 << N) - 1]; 38 return 0; 39 }

轉載于:https://www.cnblogs.com/Itst/p/9833372.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的NowCoder110E Pocky游戏 状压DP的全部內容，希望文章能夠幫你解決所遇到的問題。

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