[FHC 2016 Qualification Round]Text Editor

先備知識: Trie
首先可以把這N個字建成一棵Trie，其中根節點編號為0
然後我們可以構造一個樹型DP，DP[u][i]代表從根節點u的子樹中印出i個字所需要的最小花費
因此我們得到以下轉移方式(v_i代表u的第i個子節點)
定義f(v,i)為從u印出v子樹內的i個字所需最小花費，一般來講，f(v,i)=DP[v][i]+(i==0?0:2)
1. 當u恰好為n個單字的尾節點，可以視為u連向一個子節點v，只是f的定義稍微修改一下，f(v,0~n)=DP[v][0~n]
2. 當u有1個子節點，DP[u][i]=f(v,i)
3. 當u有2個子節點，DP[u][i]=min{f(v0,k)+f(v1,i-k), k=0~i}
4. 當u有多個子節點，可以考慮將子樹們兩個兩個合併，也就是先合併v0和v1，合出來的結果再和v2合，然後是跟v3......以此類推
因此，我們就可以根據子節點的資訊遞推出u的資訊了
答案出來了，就是DP[0][K]！

等等等，沒這麼簡單
題目範圍告訴你，這棵Trie最多會有100000個節點！
計算每個節點的DP值需要K^2的時間
這樣計算量就會多達10^12(要記的還有一個T呦~)
那怎麼辦呢？
可以注意到，上述情況2.可以再濃縮
因此，我們可以把很長很長的一條鏈濃縮成加邊權的邊，這樣f(v,i)就變成了DP[v][i]+(i==0?0:e.cost)了
濃縮過後的樹最多有2N個節點，複雜度O(N K^2)
可能有人想問，為甚麼是2N呢？
因為每加一個單字進來最多會讓Trie多一個分岔和一個葉節點嘛
證明完成(?)

所以，我們只要把這些單字建成一棵Trie，把這棵Trie重建成一個邊有權重的圖，在這張圖上作樹型DP，然後這個DP在遞推的時候要兩兩合併，就好(?)了

實作上有諸多細節要注意，尤其是重建圖的過程極為容易出錯，DP在合併的時候也容易混亂，也要注意維護單字節點的性質，至於剩下的Ø就沒什麼要注意的地方了

這個code是否還有其他BUG，真正結果要等比賽結束後才知道Orz

ps.最後四題全對耶真開心 :D

(官方的O(N^2 K)解法單純多了可以去看一下www

code:

#include<cstdio>
#include<cassert>
#include<map>
#include<vector>
#define scanf(x,...) assert(scanf(__VA_ARGS__)==x)
using namespace std;
const int INF=2147483647;
void getmin(int &a,const int b){if(b<a)a=b;}
struct Edge
{
 int nxt,cost;
 Edge(){}
 Edge(const int _n,const int _c):nxt(_n),cost(_c){}
};
vector<int>Merge(const vector<int>&a,const vector<int>&b)
{
 vector<int>ans;
 ans.resize(((int)a.size()-1)+((int)b.size()-1)+1,INF);
 for(int i=0;i<(int)a.size();i++)for(int j=0;j<(int)b.size();j++)getmin(ans[i+j],a[i]+b[j]);
 return ans;
}
vector<vector<Edge> >ET;
vector<int>WORD;
void Dfs(const int u,vector<int>&dp)
{
 dp.clear();
 for(int i=0;i<=WORD[u];i++)dp.push_back(i);
 for(const Edge &e:ET[u])
 {
  vector<int>tmp;
  Dfs(e.nxt,tmp);
  for(int i=1;i<(int)tmp.size();i++)tmp[i]+=e.cost*2;
  dp=Merge(dp,tmp);
 }
// printf("u=%d,word=%d\n",u,WORD[u]);
// for(auto v:dp)printf(" %d",v);puts("");puts("");
}
int NewVertex()
{
 const int ans=ET.size();
 ET.push_back(vector<Edge>());
 WORD.push_back(0);
 return ans;
}
struct Trie
{
 vector<map<char,int> >CH;
 vector<int>CNT;
 void clear(){CH.clear(),CNT.clear();Expand();}
 void Expand(){CH.push_back(map<char,int>()),CNT.push_back(0);}
 int GetNxt(const int u,const char c)
 {
  const auto it=CH[u].find(c);
  if(it==CH[u].end())
  {
   const int sz=CH.size();
   Expand();
   return CH[u][c]=sz;
  }
  else return it->second;
 }
 void Insert(char *str)
 {
  int u=0;
  for(int i=0;str[i];i++)u=GetNxt(u,str[i]);
  CNT[u]++;
 }
 void BuildGraph(const int u,const int gu,const int cost)
 {
  assert(gu<(int)ET.size());
  if((int)CH[u].size()==0)
  {
   const int now=NewVertex();
   ET[gu].push_back(Edge(now,cost));
   WORD[now]+=CNT[u];
  }
  else if((int)CH[u].size()==1&&CNT[u]==0)BuildGraph(CH[u].begin()->second,gu,cost+1);
  else
  {
   const int now=NewVertex();
   ET[gu].push_back(Edge(now,cost));
   WORD[now]+=CNT[u];
   for(const auto &it:CH[u])BuildGraph(it.second,now,1);
  }
 }
}TRIE;
int N,K;
int main()
{
 freopen("in.txt","r",stdin);
 freopen("out.txt","w",stdout);
 int testcase;scanf(1,"%d",&testcase);
 while(testcase--)
 {
  scanf(2,"%d%d",&N,&K);
  TRIE.clear();
  for(int i=0;i<N;i++)
  {
   static char tmp[100001];scanf(1,"%s",tmp);
   TRIE.Insert(tmp);
  }
  ET.clear(),WORD.clear();
  TRIE.BuildGraph(0,NewVertex(),0);
  vector<int>dp;
  Dfs(0,dp);
  assert((int)dp.size()==N+1);
//  for(int v:dp)printf("%d ",v);puts("");
  static int kase=1;
  printf("Case #%d: %d\n",kase++,dp[K]);
 }
 scanf(-1,"%d",&testcase);
 return 0;
}