傳送門

題意：

給你$n$個物品，讓你將其分成任意組，在同一個組內的$i,j$會獲得$a_{i,j}$的收益，讓你選擇一種分組方案使得收益最大。

$1\le n\le 16,|a_{i,j}|\le 1e9$

思路：

考慮到$n$很小，所以考慮狀壓$dp$，設$dp[i]$代表選的數狀態為$i$的時候的最大收益，那么下面的問題就是如何合并轉移了。。

我們利用像區間$dp$一樣的思路枚舉斷點，這里是枚舉當前狀態$state$的子集，設枚舉的子集是$i$，那么$state?i$就是另一個子集，我們只要保證算$state$的時候其子集的最優解已經被求出來即可，轉移就是$f[state]=max(f[state],f[i]+f[state?i])$。

復雜度$O(n^2{2}^n+3^n)$，因為枚舉子集的總復雜度是$3^n$。

#include<bits/stdc++.h> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define Mid (tr[u].l+tr[u].r>>1) #define pb push_back using namespace std;const int N=20,INF=0x3f3f3f3f,mod=1e9+7; typedef long long LL;int n; int a[N][N]; LL dp[1<<N],val[1<<N];void solve() {cin>>n;for(int i=0;i<n;i++) {for(int j=0;j<n;j++) {cin>>a[i][j];}}for(int state=1;state<1<<n;state++) {for(int i=0;i<n;i++) {for(int j=i+1;j<n;j++) if((state>>i&1)&&(state>>j&1)) {val[state]+=a[i][j];}}}for(int state=1;state<1<<n;state++) {dp[state]=val[state];for(int j=state&(state-1);j;j=(j-1)&state) {dp[state]=max(dp[state],dp[state^j]+dp[j]);}}cout<<dp[(1<<n)-1]<<endl; }int main() {int _=1;while(_--) {solve();}}

總結

以上是生活随笔為你收集整理的Educational DP Contest U - Grouping 状压dp的全部內容，希望文章能夠幫你解決所遇到的問題。

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