POJ 2292 - Optimal Keypad

http://poj.org/problem?id=2292

概要

与えられた M 個の単語を入力するのにボタンを押す回数が最小になるように，携帯電話のキーを割り当てたい．

そのために，a, b, ..., z, +, *, /, ? という30個の文字が書かれたテープを考え，これを12個に最適に分割する問題を考える． ここから11個の文字を選び，それらの文字の直前でテープを切り，それぞれが各ボタンに左から順に割り当てられる．

最適に切ったとき，その11個の文字を答える．複数の答えがある場合には辞書順で最小のものを答える．

制約

解法

dp[i][k] = k 個めの区切りを i 番目の文字にしたときの最小コスト

という DP 表を埋めた後，経路復元する．

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   static int c2i[128];
 8   static char i2c[30];
 9   for (int i = 0; i < 26; i++) {
10     c2i['a'+i] = i;
11     i2c[i] = 'a'+i;
12   }
13   c2i['+'] = 26;
14   i2c[26] = '+';
15   c2i['*'] = 27;
16   i2c[27] = '*';
17   c2i['/'] = 28;
18   i2c[28] = '/';
19   c2i['?'] = 29;
20   i2c[29] = '?';
21 
22   ios::sync_with_stdio(false);
23   int T;
24   cin >> T;
25   while (T-- > 0) {
26     int M;
27     cin >> M;
28     vector<int> cnt(30, 0);
29     for (int i = 0; i < M; i++) {
30       string s;
31       cin >> s;
32       for (string::const_iterator it = s.begin(); it != s.end(); ++it) {
33         ++cnt[c2i[int(*it)]];
34       }
35     }
36 
37     static const int INF = 10000000;
38     vector<vector<int> > dp(30, vector<int>(12, INF));
39     vector<vector<int> > dp_prev(30, vector<int>(12, -1));
40     dp[0][0] = 0;
41 
42     for (int k = 1; k < 12; k++) {
43       for (int i = 0; i < 30; i++) {
44         for (int j = 0; j < i; j++) {
45           int s = 0;
46           for (int x = j; x < i; x++) {
47             s += cnt[x]*(x-j);
48           }
49           if (dp[j][k-1]+s < dp[i][k]) {
50             dp[i][k] = dp[j][k-1]+s;
51             dp_prev[i][k] = j;
52           }
53         }
54       }
55     }
56     int mincost = INF;
57     int idx = -1;
58     for (int i = 0; i < 30; i++) {
59       int s = 0;
60       for (int j = i; j < 30; j++) {
61         s += cnt[j] * (j-i);
62       }
63       if (dp[i][11]+s < mincost) {
64         mincost = dp[i][11]+s;
65         idx = i;
66       }
67     }
68     char ans[12];
69     ans[11] = '\0';
70     for (int k = 11; k > 0; k--) {
71       ans[k-1] = i2c[idx];
72       idx = dp_prev[idx][k];
73     }
74     cout << ans << endl;
75   }
76   return 0;
77 }
poj/2292.cc