TopCoder SRM 607 Div1 Medium CombinationLockDiv1

問題

ダイアル式のロックがある。
現在表示されている数字はsで、これをtにしたい。

一回の操作では、それぞれの数字を+1または-1することができて、9を+1すると0, 0を-1すると9になる。
また、連続している位置にある数字は同じ回転ならいくつでも同時に操作を行うことができる。

sをtにするために必要な操作の回数の最小値を求めよ。

制約条件

sとtの長さは同じで2500以下

方針

とてもよくある、区間を打ち消す操作は分割しても同じですよ系のDP.

ある区間に
＋＋＋＋＋＋＋＋＋
０００−−−０００
という操作をしたとする。これは、
＋＋＋０００＋＋＋
という操作をしたのと同じ。

すなわち、逆向きの操作をして打ち消された場合、打ち消す操作はなかったことにして、
代わりに打ち消さない操作を二つの区間に別々に適用したと考えても同じ。

なのでdp[位置][累積のプラスの回数（またはマイナスの回数）] := コストの最小値
というDPをすればいいだけ。
累積のプラスの回数は最大で20 * n（マイナスもあるので）
で、全体でO(n^2)時間の計算量。

ソースコード

int n, p[2500], q[2500];
int dp[2][50001];

class CombinationLockDiv1 {
	public:
	int minimumMoves(vector <string> P, vector <string> Q) {
		string s, t;
		rep(i, P.size()) s += P[i];
		rep(i, Q.size()) t += Q[i];
		n = s.size();
		rep(i, n){
			p[i] = s[i] - '0';
			q[i] = t[i] - '0';
		}
		
		rep(j, 50001) dp[0][j] = inf;
		dp[0][25000] = 0;
		
		rep(i, n){
			rep(j, 50001) dp[i&1^1][j] = inf;
			for(int j = -25000; j <= 25000; j++){
				int &cur = dp[i&1][j + 25000];
				if(cur == inf) continue;
				
				int a = q[i] - (p[i] + 26000 + j) % 10;
				rep(k, 2){
					if(j + a <= 25000 && j + a >= -25000){
						int &next = dp[i&1^1][j + a + 25000];
						int cost = 0;
						if((j >= 0) == (j+a >= 0)) cost = max(0, abs(j+a) - abs(j));
						else cost = abs(j+a);
						next = min(next, cur + cost);
					}
					if(a == 0) break;
					if(a > 0) a -= 10;
					else a += 10;
				}
			}
		}
		int ans = inf;
		rep(i, 50001) ans = min(ans, dp[n&1][i]);
		return ans;
	}
};