[CF 543C] Remembering Strings

作法：

我一開始的想法是，對於每個字串，我們可以選一個位置把他改掉，使得這個字串一定可以滿足條件，因為字串的個數小於字母的個數。而對於每一行來說，我們可以做的決策就是選一些字串並且把那個位置改成星號，代表等一下一定會變得不一樣的意思，並且可以算出這樣的決策會讓哪些字串變得滿足條件。有了轉移就可以位元 DP 了，記 $dp[ i ][ j ]$ 代表只考慮前 $i$ 行，並且已滿足條件的字串集合為 $j$ 時至少需要花費多少。但這樣每一行都會有 $O( 2^n )$ 種決策，會讓複雜度爆掉，於是我就卡到比賽結束了......後來去看詳解才知道，其實我們可以把決策都拆開，例如假設一行裡面有 $6$ 個 $a $，其中一個決策是把 4 個 $a$ 換成星號，那麼就可以把他拆成 $4 $種決策，每種分別是把對應位置的 $a $換成星號。而如果是把 $5$ 個 $a$ 換成星號的決策，就會讓 $6$ 個字串都變成符合條件的，總共有 $6$ 種取法，但他們的功能都一樣，所以只要取會讓花費最少的那個方案就好了。而像取好幾個 $a$ 和好幾個 $b$ 的決策，也可以把他拆成取好幾個 $a$ 和取好幾個 $b$ ，這樣剩下的決策總數就剩下 $O( m )$ 了（對於那些達到相同功能的決策都取他們的 $min$ 值），所以就可以在 $O( m^2  2^n )$ 的時間內DP完了。而至於為什麼這裡的DP可以這樣拆，是因為狀態在轉移時是從 $j$ 轉移到 $j | x$ ，其中 $x$ 代表這次決策可以造成哪些字串變成符合條件的。

code :

#include<bits/stdc++.h>
#define INF 1000000000
using namespace std;
const int maxn=30 ;
 
int dp[1<<20],cost[1<<20] ;
char G[maxn][maxn] ;
int a[maxn][maxn] ;
 
int ma[maxn],bit[maxn],sum[maxn] ;
int F[maxn*maxn],S[maxn*maxn] ;
main()
{
    int n,m ; scanf("%d%d",&n,&m) ;
    for(int i=0;i<n;i++) scanf("%s",G[i]+1) ;
    for(int i=0;i<n;i++) for(int j=1;j<=m;j++)
        scanf("%d",&a[i][j]) ;
 
    fill(cost,cost+(1<<n),INF) ;
    for(int i=0;i<n;i++) for(int j=1;j<=m;j++)
        cost[1<<i]=min(cost[1<<i],a[i][j]) ;
    for(int i=1;i<=m;i++)
    {
        for(int j=0;j<26;j++) ma[j]=-1 , bit[j]=0 , sum[j]=0 ;
        for(int j=0;j<n;j++)
        {
            int c=G[j][i]-'a' ;
            bit[c]|=(1<<j) ;
            sum[c]+=a[j][i] ;
            ma[c]=max(ma[c],a[j][i]) ;
        }
        for(int j=0;j<26;j++) if(bit[j])
            cost[bit[j]]=min(cost[bit[j]],sum[j]-ma[j]) ;
    }
 
    int cnt=0 ;
    for(int i=0;i<(1<<n);i++) if(cost[i]!=INF)
        F[cnt]=i , S[cnt]=cost[i] , cnt++ ;
    fill(dp,dp+(1<<n),INF) ; dp[0]=0 ;
    for(int i=0;i<(1<<n)-1;i++) if(dp[i]!=INF)
        for(int j=0;j<cnt;j++) dp[i|F[j]]=min(dp[i|F[j]],dp[i]+S[j]) ;
    printf("%d\n",dp[(1<<n)-1]) ;
}