Codeforces 174D (283D) Cows and Cool Sequences

問題

あとで。眠い。

制約条件

方針

ソースコード

ll a[5000];
int n, dp[5000], two[5000];

int main(){
	cin >> n;
	rep(i, n){
		cin >> a[i];
		two[i] = __builtin_ctzll(a[i]);
	}
	int ans = n;
	rep(i, n){
		dp[i] = i;
		rep(j, i){
			ll c = a[i] >> min(two[i], i - j - 1);
			if(c % 2 == 0 && a[j] % c == c/2 || c % 2 && a[j] % c == 0)
			dp[i] = min(dp[i], dp[j] + i - j - 1);
		}
		ans = min(ans, dp[i] + n - i - 1);
	}
	cout << ans << endl;
	return 0;
}