[Facebook Hacker Cup Round 2] Autocomplete Strikes Back

((因為寫完第一題後不小心按到下載第二題的測資，所以才寫了這題(?)

作法：在 Trie 上DP，dp[ x ][ i ] 代表在 x 的子樹裡選 i 個單字的最小打字數(打的字都在這棵子樹裡)，在DP前先把樹拆點轉成二元樹，這樣就可以 O(k) 轉移，不過聽說在每個結點都作一次背包問題也可以過，這樣變O(kk)轉移。

(把樹轉成二元樹的作法在 IOI2005 Rivers (HOJ 326) 也有用到，前幾天剛好寫到那題...)

code :

#include<bits/stdc++.h>
using namespace std;
 
int id(char c)
{
    return c-'a' ;
}
 
int ch[20001][26],val[20001],ccnt ;
void insert(char *t)
{
    int now=0 , len=strlen(t) ;
    for(int i=0;i<len;i++)
    {
        int u=id(t[i]) ;
        if(!ch[now][u])
        {
            ccnt++ ; memset(ch[ccnt],0,sizeof(ch[ccnt])) ;
            ch[now][u]=ccnt ;
        }
        now=ch[now][u] ;
    }
    val[now]=1 ;
}
 
vector<int> v[100001] ;
int w[200001] ;
char s[20001] ;
 
int dp[100001][101] ;
int DP(int x,int num)
{
    if(num==0) return 0 ;
    if(num==1) return 1 ; /// ~~~~~~~~~~~
    if(v[x].empty())
    {
        return 20001 ;
        //if(val[x]) return num==1 ? w[x] : 20001 ;
        //else return 20001 ;
    }
    if(dp[x][num]!=-1) return dp[x][num] ;
 
    int &ans=dp[x][num] ; ans=20001 ;
    if((int)v[x].size()==1)
    {
        if(num==1) return (ans=1) ;
        ans=min(ans,num*w[x]+DP(v[x][0],num)) ;
        if(val[x]) ans=min(ans,num*w[x]+DP(v[x][0],num-1)) ;
        return ans ;
    }
 
    ans=min(ans,num*w[x]+DP(v[x][0],num)) ;
    ans=min(ans,num*w[x]+DP(v[x][1],num)) ;
    for(int i=1;i<num;i++)
        ans=min(ans,num*w[x]+DP(v[x][0],i)+DP(v[x][1],num-i)) ;
    if(!val[x]) return ans ;
 
    ans=min(ans,num*w[x]+DP(v[x][0],num-1)) ;
    ans=min(ans,num*w[x]+DP(v[x][1],num-1)) ;
    for(int i=1;i<num-1;i++)
        ans=min(ans,num*w[x]+DP(v[x][0],i)+DP(v[x][1],num-i-1)) ;
    return ans ;
}
 
main()
{
    freopen("C.txt","r",stdin) ;
    freopen("Cout.txt","w",stdout) ;
    int T ; scanf("%d",&T) ;
    int tc=0 ;
    while(T--)
    {
        ccnt=0 ; memset(ch[0],0,sizeof(ch[0])) ;
        memset(val,0,sizeof(val)) ;
        memset(w,0,sizeof(w)) ;
        for(int i=0;i<=100000;i++) v[i].clear() ;
        int n,k ; scanf("%d%d",&n,&k) ;
        while(n--)
        {
            scanf("%s",s) ;
            insert(s) ;
        }
 
        for(int i=1;i<=ccnt;i++) w[i]=1 ;
        for(int i=0;i<=ccnt;i++) for(int j=0;j<26;j++) if(ch[i][j])
            v[i].push_back(ch[i][j]) ;
 
        for(int i=0;i<=ccnt;i++)
        {
            int sz=v[i].size() ;
            if(sz<=2)
            {
                if(val[i]) w[i]=1 ;
                continue ;
            }
 
            int tmp=ccnt+1 ;
            for(int j=1;j<sz-2;j++)
            {
                ccnt++ ;
                v[ccnt].push_back(v[i][j]) ;
                v[ccnt].push_back(ccnt+1) ;
            }
            ccnt++ ;
            v[ccnt].push_back(v[i][sz-2]) ;
            v[ccnt].push_back(v[i][sz-1]) ;
            v[i][1]=tmp ; v[i].resize(2) ;
        }
 
        memset(dp,-1,sizeof(dp)) ;
        printf("Case #%d: %d\n",++tc,DP(0,k)) ;
    }
}