Hatena::Grouptopcoder

yaottiの日記

2010-03-11

SRM 156 DIV2再び

| 23:14

hard

Editorial読んでもう一度挑戦.というかそのままコードにしただけ.

memoize!

class WordParts {
public:
    string orig;
    string cmp;
    vector <string> dict;
    int memo[100];
    int minParts(int pos) {
        if (memo[pos] != -1) return memo[pos];
        if (pos == (int)cmp.size()) return 0;
        int ret = 10000;
        LP(dict) {
            if (cmp.substr(pos, dict[i].size()) == dict[i]) { // prefix
                ret = min(ret, 1+minParts(pos+dict[i].size()));
            }
        }
        memo[pos] = ret;
        return ret;
    }
    void setUpDict() {
        // prefix
        dict.clear();
        for (int i = 1; i < (int)orig.size(); i++) {
            dict.push_back(orig.substr(0, i));
        }
        for (int i = 1; i < (int)orig.size(); i++) {
            dict.push_back(orig.substr(i));
        }
        dict.push_back(orig);
    }
    int partCount(string original, string compound) {
        cmp = compound;
        orig = original;
        setUpDict();
        memset(memo, -1, sizeof(memo));
        int ret = minParts(0);
        return  ret < 1000 ? ret : -1;
    }
}