5

私はこの問題を解決しています -

a、b、c で​​構成される文字列が与えられた場合、隣接する 2 つの異なる文字を取り、3 番目の文字に置き換えることができます。たとえば、「a」と「c」が隣接している場合、「b」に置き換えることができます。この操作を繰り返し適用して得られる最小の文字列は?

これで、次の再帰的ソリューションを作成しました (効率的とはほど遠い) が、それをトップダウンまたはボトムアップのソリューションに変換したいと考えています。

問題: メモ化のための表形式の構造を考え出すことができません。結果の文字列の長さだけを出力する必要がありますが、実際に問題を解決せずにどうすれば解決できますか。弦が少なくなってきましたが、保管方法は？

DPソリューションまたはメモ化のヒントは素晴らしいでしょう!

編集多くの人がトップダウンのメモ化ソリューションを思いついたので、ボトムアップも試してください。

#include <iostream>
#include <string>

using namespace std;

string reduce(string s)
{
    if (s.length() <= 1)
        return s;

    int k;
    char c = s[0];
    string min = s;
    for (k = 1; k < s.length() && c; ++k)
        if (s[k] != c)
            c = 0;
    if (c)
        return s;

    if (s.length() == 2){
        if (s[0] != 'a' && s[1] != 'a')
            s[0] = 'a';
        else if (s[0] != 'b' && s[1] != 'b')
            s[0] = 'b';
        else if (s[0] != 'c' && s[1] != 'c')
            s[0] = 'c';
        s.resize(1);
        return s;
    }

    for (k = 1; k < s.length(); ++k){
        string s1 = reduce(s.substr(0, k));
        string s2 = reduce(s.substr(k));

        if (s1.length() + s2.length() < min.length())
            min = s1 + s2;
        if (!s1.empty() && !s2.empty() && s1.back() != s2.front()){
            if (s1.back() != 'a' && s2.front() != 'a')
                s1.back() = 'a';
            else if (s1.back() != 'b' && s2.front() != 'b')
                s1.back() = 'b';
            else if (s1.back() != 'c' && s2.front() != 'c')
                s1.back() = 'c';
            s1 = reduce(s1 + s2.substr(1));
            if (s1.length() < min.length())
                min = s1;
        }

    }
    return min;
}

int main()
{
    string input;
    cin >> input;
    cout << reduce(input) << endl;
    return 0;
}
4

7 に答える 7

2

私は少し怠惰すぎて問題を考えることができませんが、十分に機能することが多いメモ化へのアプローチを紹介します。

直接再帰するのではなく、相互再帰を導入します。

std::string reduce(std::string const &s)
{
    // ...
    string s1 = reduce_memo(s.substr(0, k));
    string s2 = reduce_memo(s.substr(k));
    // ...
}

ここでreduce_memo、ハッシュテーブル、つまり、unordered_mapサブ問題をそれらのソリューションにマッピングするを維持します。

// static is incredibly ugly, but I'll use it here for simplicity
static std::unordered_map<std::string, std::string> memo;

std::string reduce_memo(std::string const &s)
{
    try {
        return memo.at(s);
    } except (std::out_of_range const &) {
        std::string r = reduce(s);
        memo[s] = r;
        return r;
    }
}

C ++ 98でプログラミングする場合は、std::mapの代わりにを使用してunordered_mapください。

于 2012-07-28T11:00:36.073 に答える
1

reduce(s)の結果をに保存することで、ソリューションをメモ化できますmap<string,string>。

string reduce(string s, map<string,string>& memo) {
    if (memo.count(s)) {
        return memo[s];
    }
    // The rest of your code follows...
    memo[s] = min;
}
于 2012-07-28T11:02:22.333 に答える
1

これで問題は解決しませんが、次のことに気付きました。

if (s.length() == 2){
    if (s[0] != 'a' && s[1] != 'a')
        s[0] = 'a';
    else if (s[0] != 'b' && s[1] != 'b')
        s[0] = 'b';
    else if (s[0] != 'c' && s[1] != 'c')
        s[0] = 'c';
    s.resize(1);
    return s;
}

問題のステートメントに従って機能しません：

隣接する2 つ の異なる文字を取り、それを3 番目の文字に置き換えることができます。

文字列を考えてみましょうs = "bb"。も等しくs[0]もありません。これは、条件が文字列に対して評価されることを意味します。これは、同じ値の連続する文字の任意の文字列に当てはまります。s[1]'a's[0] != 'a' && s[1] != 'a'true"bb""bb""cc"

おそらく、2 つの連続する文字の差を取り、それらがゼロでないかどうかを確認できる状態である可能性があります。

于 2012-07-28T11:16:10.980 に答える
0

絶対最小値は1です。ただし、文字列と置換ルールの詳細により、との間が生成1される場合があります。nここnで、は文字列の長さです。

特定の例では、可能な限り最小の文字はn/2、2文字を取得して1に置き換えるため（これ以上置き換えることはできません）"acacacacacacacac"、最良の場合でも、2倍の削減しか達成できません。

于 2012-07-28T10:58:30.593 に答える
0

問題から私が理解したことは何でも、解決策はあるべきです

入力の長さ - すべての入力文字が同じである場合

aaaaa - 5
bbb - 3

その他の場合は 1 です。

問題の一部が欠けている場合は修正してください。

于 2012-07-28T10:54:21.400 に答える
0

競合プログラミングワークショップで同様の問題を解決しましたが、実際、提案されたソリューションは十分に高速ではありませんでした。

私の解決策は、そのようなベクトルを作成することでした:

string s;
cin >> s;
int length = s.length();
vector<vector<int> > v(length, vector<int>(length)); // 2d array of size length*length.

どこからのv[i][j]部分文字列が到達できる最小の長さになります。ijs

後は、このテーブルのサイズを大きくするだけです。それが役に立ったことを願っています。

于 2012-07-28T11:15:42.833 に答える
0 
"a...a" (“a" * n) == > n
"b...b" (“b" * n) == > n
"c...c" (“c" * n) == > n
 any other ==> 1 or 2 with my greedy algorithm.

この貪欲なアルゴリズムで 2 が得られた場合、それが入力文字列の最小の結果であることを証明できません。

貪欲なアルゴリズム

while the last two is the same character { // the number of the same characters
    find the last replaceable pair         // at the tail will decrease until
        reduce them                        // it become 1
}

while find the first replaceable pair
    reduce them
于 2012-07-28T11:58:57.610 に答える