TopCoder SRM 596 Div1 Easy IncrementAndDoubling

問題

長さnの整数の列aがあり、最初はa[i]はすべて0
これを以下の操作を繰り返してa[i]をb[i]に一致させたい。
必要な操作の回数の最小値を求めよ。

• すべての要素を2倍する
• 一つの要素を選んで+1する

制約条件

n≦50
0≦b[i]≦1000

方針

1. 1 →　2倍×α回　→ +1とやるのが一番効率がよい。

２倍にするところは、αが一番必要な奴の回数だけでよい十分。
少ない奴は最初の+1をその分だけ遅らせればいいため。

で、最初の議論から、greedyに二倍できるだけするのが良いんだけど、DPでやってしまった。
dp[i][j]:=i回2倍を使ってjを作るのにかかる加算の回数の最小値
を更新した。

ソースコード

int dp[20][1100];

class IncrementAndDoubling {
	public:
	int getMin(vector <int> desiredArray) {
		
		int n = desiredArray.size();
		int ans = inf;
		
		rep(i, 20) rep(j, 1100) dp[i][j] = inf;
		dp[0][0] = 0;
		
		rep(i, 20) rep(j, 1100) if(dp[i][j] < inf){
			if(j + 1 < 1100) dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + 1);
			if(i < 18 && j * 2 < 1100) dp[i + 1][j * 2] = min(dp[i + 1][j * 2], dp[i][j]);
		}
		
		rep(mul, 20){
			ll res = mul;
			rep(i, n){
				int mn = inf;
				rep(j, mul + 1) mn = min(mn, dp[j][desiredArray[i]]);
				res += mn;
			}
			ans = min((ll)ans, res);
		}
		
		return ans;
	}
};