読者です 読者をやめる 読者になる 読者になる

TopCoder SRM 518 Div1 Medium: ConvexSequence

解法

愚直オブザイヤー。お前その解法が通っちゃダメだろ……!!

コード

import java.util.Arrays;

public class ConvexSequence {

	public long getMinimum(int[] a) {
		int N = a.length;
		int[] b = Arrays.copyOf(a, N);
		while (true) {
			boolean end = true;
			for (int i = 1; i < N - 1; i++) {
				int mid = (b[i - 1] + b[i + 1]) / 2;
				if (mid < b[i]) {
					b[i] = mid;
					end = false;
				}
			}
			if (end) {
				break;
			}
		}
		long ans = 0;
		for (int i = 0; i < N; i++) {
			ans += a[i] - b[i];
		}
		return ans;
	}

}