AOJ 2266: Cache Strategy

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

箱が1つなら簡単。
箱がmつの時はM-1個の箱がコストを節約するために使えると考えられる。
どれくらいコストを節約できるか考えよう。
あるボールを時刻sに入れ、次に入れる時刻をtとしよう。
すると時刻[s+1,t)においてボールを入れ続けることが出来ればボールのコストを削減できる。
なのでこのような区間の重なりがM-1以上にならないようにコストを最大化する問題になる。

これは蟻本のPOJ 3680と同じ問題なので解けた。

問題の咀嚼が難しい。こういう言い換えは思いつかない。
ボールだけに注目したり、箱のみに注目したり…みたいに「部分」に注目すると気付きやすい?

解説を読んでいると
http://blog.hatena.ne.jp/omochangram/omochan.hatenablog.com/edit?entry=8599973812276127257
と少し似ているなと思った。

使っているんだけど使っていないことにしたり、使うものをストックしといて後に使ったり。時系列でものを使っていくときのテクニック？

int M, N, K;
int A[MAX_N];
vector<int> B[MAX_N];

void solve() {
	cin >> M >> N >> K;
	int res = 0;
	MCF::init(K);
	rep(i, 0, N) cin >> A[i];
	rep(i, 0, K) {
		int a; cin >> a; a--;
		B[a].push_back(i);
		res += A[a];
	}
	rep(i, 0, N) {
		if((int)B[i].size() <= 1) continue;
		rep(j, 0, (int)B[i].size() - 1) {
			int n1 = B[i][j], n2 = B[i][j + 1];
			if(n1 + 1 != n2) MCF::add_edge(n1 + 1, n2, 1, -A[i]);
			else res -= A[i];
		}
	}
	rep(i, 0, K - 1) MCF::add_edge(i, i + 1, M, 0);
	cout << res + MCF::get(0, K - 1, M - 1) << "\n";
}

How to Create a Good Gameは何とかして倒したい。