AOJ 2157 Dial Lock

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2157

問題概要

数列の連続した区間に同じ数を足し引きする操作によって，ある数列を目的に数列に一致させたい．このとき，目的を達成する最小の操作回数を求めよ．

制約 : 数列の長さは10以下．

解法

全探索．前から順番に，数字を合わせて行けば良さそう．
なぜなら，数字をずらしていく操作列を考えたときに，それらの順番を入れ替えても最終的な状態は変化しないから．
しかし，例えば最初の数字を複数回の操作で合わせるような操作を考える必要があるだろうか？
これは考える必要が無いことが分かる．なぜなら，例えば3回の操作（それぞれ，区間 [0, a]，[0, b]，[0, c] を操作する．ただし，a < b < c としてよい．a == b なら無駄だし，最初に述べたように操作順は自由で良いため．）で最初の数字をあわせることを考える．
このとき，それぞれの操作で，x, y, z だけずらすとする．この時，[0, a] は x + y + z だけ，(a, b] は y + z だけ，(b, c] は z だけずれたことになる．これは，[0, a] を x + y + z だけ，(a, b] を y + z だけ， (b, c] を z だけずらす操作と同値であり，これらの操作回数は等しい．
これはつまり，ある桁をあわせることを目標とする時，その桁を一回の操作で合わせることだけ考えればよいことにほかならない．
以上から，前の桁から目的の数字に合わせ，かつ先頭の数字は一回の操作で合わせることを考えればよいことになる．
あとは，注目している区間の先頭の数字を合わせるためにずらす操作を，どの区間で行うかを全探索すれば，最終的な答えが求まる．ずらした後隣の数字を考えるので，DFSで実装すると楽．
計算量は O(k!) である．ただ，以下の実装だと string のコピーが無視できないかもしれない（それでもぎりぎり間に合う）．

ソースコード

#include <iostream>
#include <string>
using namespace std;

int dfs(int i, string s, string const& g, int cnt) {
    if(i >= s.size()) {
        return cnt;
    }
    if(s[i] == g[i]) {
        return dfs(i+1, s, g, cnt);
    }
    int res = 1e9;
    int t = (g[i] - s[i] + 10) % 10;
    for(int j=i; j<s.size(); ++j) {
        s[j] = '0' + ((s[j] - '0' + t) % 10);
        res = min(res, dfs(i+1, s, g, cnt+1));
    }
    return res;
}

int main() {
    int k;
    while(cin >> k, k) {
        string s, g;
        cin >> s >> g;
        cout << dfs(0, s, g, 0) << endl;
    }
}