2014年1月31日

UVa 11552 - Fewest Flops

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

int price[1111][26][26];
int dp[1111][26];

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int K;
    char S[1111];
    scanf("%d%s", &K, S);
    int N = strlen(S) / K;
    vector<int> ch[1111];
    for (int i = 1; i <= N; i++) {
      int rec[26] = {};
      for (int j = (i - 1) * K; j < i * K; j++) {
        rec[S[j] - 'a']++;
      }
      for (int j = 0; j < 26; j++) {
        if (rec[j]) {
          ch[i].push_back(j);
        }
      }
      int type = ch[i].size();
      for (int j = 0; j < type; j++) {
        for (int k = 0; k < type; k++) {
          int h = ch[i][j], t = ch[i][k];
          if (h == t) {
            if (type == 1) {
              price[i][h][t] = 1;
            } else {
              if (rec[h] > 1) {
                price[i][h][t] = type + 1;
              } else {
                price[i][h][t] = 1e8;
              }
            }
          } else {
            price[i][h][t] = type;
          }
        }
      }
    }
    int ans = 1e8;
    for (int i = 1; i <= N; i++) {
      for (int j = 0; j < ch[i].size(); j++) {
        int t = ch[i][j];
        dp[i][t] = 1e8;
        for (int k = 0; k < ch[i].size(); k++) {
          int h = ch[i][k];
          if (i == 1) {
            dp[i][t] = min(dp[i][t], price[i][h][t]);
          } else {
            for (int l = 0; l < ch[i - 1].size(); l++) {
              int prevT = ch[i - 1][l];
              dp[i][t] = min(dp[i][t], dp[i - 1][prevT] + price[i][h][t] - (prevT == h));
            }
          }
        }
        if (i == N) {
          ans = min(ans, dp[i][t]);
        }
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

沒有留言:

張貼留言