かなり好きな問題。

## Text Editor

### 実装

#include <iostream>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
using namespace std;
struct trie_t { trie_t *p[26]; bool exists; int count; };
trie_t *new_trie() {
trie_t *t = new trie_t;
repeat (i,26) t->p[i] = NULL;
t->exists = false;
t->count = 0;
return t;
}
trie_t *get_valid_trie(trie_t *t, char c) {
if (not t->p[c-'a']) t->p[c-'a'] = new_trie();
return t->p[c-'a'];
}
void delete_trie(trie_t *t) {
repeat (i,26) if (t->p[i]) delete_trie(t->p[i]);
delete t;
}
vector<int> bar(trie_t *t) {
vector<int> dp(t->count + 1, 1000000007);
dp[0] = 0;
if (t->exists) dp[1] = 1;
repeat (i,26) if (t->p[i]) {
vector<int> a = bar(t->p[i]);
repeat_reverse (j,dp.size()) {
repeat (k,a.size()) if (0 <= j-k) {
dp[j] = min(dp[j], dp[j-k] + a[k] + 2);
}
}
}
return dp;
}
void foo() {
int n, k; cin >> n >> k;
trie_t *root = new_trie();
repeat (i,n) {
string s; cin >> s;
trie_t *t = root;
t->count += 1;
for (char c : s) {
t = get_valid_trie(t, c);
t->count += 1;
}
t->exists = true;
}
cout << bar(root)[k] << endl;
delete_trie(root);
}
int main() {
int testcases; cin >> testcases;
repeat (testcase, testcases) {
cout << "Case #" << testcase+1 << ": ";
foo();
}
return 0;
}