jzoj 5001. 【NOI2017模擬3.4】Trie樹狀壓dp

2019-11-06 06:28:11

字體：大中小

來源：轉載

供稿：網友

題意

給出n個字符串，每個字符串的字符可以任意調換位置，問將這些字符串建一棵trie樹需要的最少節點數（包括根節點）。 n<=16,字符串總長<=10000000

分析

咋一看啥思路都沒有，其實并不難，說白了還是我太弱啦。。。復制一波題解：顯然，如果我們希望 Trie 樹的節點數盡量少，我們應該先將所有單詞公共的字母拿出來，作為 Trie 樹最上幾層的初始鏈。比如說我們有 aaab，baab 和 cab 三個單詞，我們會將 ab 挑出來，然后剩下的單詞就變成了 aa，ab，c。對于剩下的單詞，我們將其分成兩個子集，（aa，ab）和（c），并分別再計算最長的公共字母鏈。顯然，當集合中有 n 個單詞時，有 2 n種方式將這些單詞分成兩個子集。由此，我們可以用狀態壓縮 dp 解決這個問題。一個狀態由單詞的子集來描述，也就是說我們有 2 n個狀態，并計算每一種子集形成 Trie 樹需要的最少節點數，轉移時枚舉如何將子集分裂成兩個更小的子集，即可解決整個問題。整個算法總的時間復雜度為 O(3n) $O(3^n)$ 。

順帶發一波枚舉i的子集的方法：for (int j=i;j;j=(j-1)&i); 這樣就可以枚舉所有i的子集啦。

代碼

#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>#define N 35#define inf 0x3f3f3f3fusing namespace std;int bin[N],n,len[N],s[N][30],f[1048580],mn[30];char str[1000005];int main(){ freopen("trie.in","r",stdin);freopen("trie.out","w",stdout); bin[0]=1; for (int i=1;i<=16;i++) bin[i]=bin[i-1]*2; scanf("%d",&n); for (int i=0;i<n;i++) { scanf("%s",str); len[i]=strlen(str); for (int j=0;j<len[i];j++) s[i][str[j]-'a']++; } f[0]=inf; for (int i=1;i<bin[n];i++) { for (int j=0;j<n;j++) if (i&bin[j]) f[i]+=len[j]; memset(mn,inf,sizeof(mn)); for (int j=0;j<n;j++) if (i&bin[j]) for (int k=0;k<26;k++) mn[k]=min(mn[k],s[j][k]); int mx=0; for (int j=0;j<26;j++) mx+=mn[j]; for (int j=i;j;j=(j-1)&i) f[i]=min(f[i],f[j]+f[i-j]); if (mx<f[i]) f[i]-=mx; }